Finding the Densest Common Subgraph with Linear Programming

Examensarbete för kandidatexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/245174
Download file(s):
File Description SizeFormat 
245174.pdfFulltext1.14 MBAdobe PDFView/Open
Type: Examensarbete för kandidatexamen
Bachelor Thesis
Title: Finding the Densest Common Subgraph with Linear Programming
Authors: Reinthal, Alexander
T ornqvist, Anton
Andersson, Arvid
Norlander, Erik
Stållhammar, Philip
Norlin, Sebastian
Abstract: This thesis studies the concept of dense subgraphs, speci cally for graphs with multiple edge sets. Our work improves the running time of an existing Linear Program (LP) for solving the Densest Common Subgraph problem. This LP was originally created by Moses Charikar for a single graph and extended to multiple graphs (DCS LP) by Vinay Jethava and Niko Beerenwinkel. This thesis shows that the run time of the DCS LP can be shortened considerably by using an interior-point method instead of the simplex method. The DCS LP is also compared to a greedy algorithm and a Lagrangian relaxation of DCS LP.We conclude that the greedy algorithm is a good heuristic while the LP is well suited to problems where a closer approximation is important.
Keywords: Data- och informationsvetenskap;Informations- och kommunikationsteknik;Computer and Information Science;Information & Communication Technology
Issue Date: 2016
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/245174
Collection:Examensarbeten för kandidatexamen // Bachelor Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.