Largest Chordal and Interval Subgraphs Faster Than 2 n
Largest Chordal and Interval Subgraphs Faster Than 2 n
We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $O(2^{��n})$ for some $��<1$. These are the first algorithms breaking the trivial $2^n n^{O(1)}$ bound of the brute-force search for these problems.
The preliminary version of this work appeared in the proceedings of ESA 2013
- Physical Sciences Division Russian Federation
- Saint Petersburg Academic University Russian Federation
- University of Bergen Norway
FOS: Computer and information sciences, Extremal problems in graph theory, Analysis of algorithms and problem complexity, Exact exponential algorithms, VDP::Matematikk og Naturvitenskap: 400, Maximum induced Π-subgraph, chordal graphs, 004, 510, Chordal graphs, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Interval graphs, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), exact exponential algorithms, interval graphs, maximum induced \(\Pi\)-subgraph, Data Structures and Algorithms (cs.DS), :Matematikk og Naturvitenskap: 400 [VDP]
FOS: Computer and information sciences, Extremal problems in graph theory, Analysis of algorithms and problem complexity, Exact exponential algorithms, VDP::Matematikk og Naturvitenskap: 400, Maximum induced Π-subgraph, chordal graphs, 004, 510, Chordal graphs, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Interval graphs, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), exact exponential algorithms, interval graphs, maximum induced \(\Pi\)-subgraph, Data Structures and Algorithms (cs.DS), :Matematikk og Naturvitenskap: 400 [VDP]
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!