Finding the Densest Common Subgraph with Linear Programming
[Examensarbete för kandidatexamen]
This thesis studies the concept of dense subgraphs, specically 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.
Nyckelord: Linear Programming, Graph theory, Dense Subgraphs, Densest Common Subgraph
Oracle XML Developers Kit 10.2.0.2.0 - ProductionXML-25011: Error processing XSLT stylesheet: ../index.xsl
file:////usr/local/tomcat/webapps/chex/local/xsl/output/html/normal/body.xsl<Line 340, Column 84>: XML-22021: (Error) Error parsing external document: 'Förbindelse vägras'.