Finding Induced Subgraphs via Minimal Triangulations

DOI10.4230/LIPICS.STACS.2010.2470zbMath1230.68108OpenAlexW1813769739MaRDI QIDQ3113765

Fedor V. Fomin, Yngve Villanger

Publication date: 23 January 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_1ced.html

zbMATH Keywords

minimal triangulationbounded treewidthmoderately exponential time algorithms

Mathematics Subject Classification ID

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

Related Items (41)

Faster exact algorithms for some terminal set problems ⋮ Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration ⋮ On the number of connected sets in bounded degree graphs ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ Circular convex bipartite graphs: feedback vertex sets ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ Minimal dominating sets in interval graphs and trees ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Graphs with polynomially many minimal separators ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ On the Number of Connected Sets in Bounded Degree Graphs ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Super-polynomial approximation branching algorithms ⋮ Computing hypergraph width measures exactly ⋮ Enumerating Minimal Tropical Connected Sets ⋮ Feedback Vertex Sets in Tournaments ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ Subset feedback vertex sets in chordal graphs ⋮ Enumerating minimal subset feedback vertex sets ⋮ On the number of minimal dominating sets on some graph classes ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ A note on exact algorithms for vertex ordering problems on graphs ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Contracting chordal graphs and bipartite graphs to paths and trees ⋮ Induced subgraphs of bounded treewidth and the container method ⋮ Tree independence number. I. (Even hole, diamond, pyramid)-free graphs ⋮ Contracting chordal graphs and bipartite graphs to paths and trees ⋮ On the Number of Minimal Separators in Graphs ⋮ Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ⋮ Unnamed Item ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set

This page was built for publication: Finding Induced Subgraphs via Minimal Triangulations