Finding Induced Subgraphs via Minimal Triangulations
From MaRDI portal
Publication:3113765
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
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
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, 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
