Largest Chordal and Interval Subgraphs Faster Than 2 n

DOI10.1007/978-3-642-40450-4_17MaRDI QIDQ2849310zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger, I. A. Bliznets

Publication date 17 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40450-4_17

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Largest chordal and interval subgraphs faster than \(2^n\)
• The size of chordal, interval and threshold subgraphs
• scientific article; zbMATH DE number 3847425
• Approximating the sparsest \(k\)-subgraph in chordal graphs
• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• Solving the 2-disjoint connected subgraphs problem faster than \(2^{n }\)
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs

Cited in

(5)

• Vertex deletion problems on chordal graphs
• Largest chordal and interval subgraphs faster than \(2^n\)
• Listing Chordal Graphs and Interval Graphs
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)

This page was built for publication: Largest Chordal and Interval Subgraphs Faster Than 2 n

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849310)