Large Induced Subgraphs via Triangulations and CMSO
From MaRDI portal
Publication:2954371
DOI10.1137/140964801zbMath1357.05144arXiv1309.1559OpenAlexW1968041356WikidataQ60488392 ScholiaQ60488392MaRDI QIDQ2954371
Fedor V. Fomin, Yngve Villanger, Ioan Todinca
Publication date: 13 January 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1309.1559
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
Enumerating minimal connected dominating sets in graphs of bounded chordality, An Improvement of Reed’s Treewidth Approximation, On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators, Largest chordal and interval subgraphs faster than \(2^n\), Finding optimal triangulations parameterized by edge clique cover, Structural parameterizations with modulator oblivion, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem, Finding a maximum minimal separator: graph classes and fixed-parameter tractability, iTri: index-based triangle listing in massive graphs, Summarized bit batch-based triangle listing in massive graphs, Treewidth versus clique number. II: Tree-independence number, On the tractability of optimization problems on \(H\)-graphs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Solving Graph Problems via Potential Maximal Cliques, Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs, Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes, A meta-theorem for distributed certification, Unnamed Item, Vertex deletion problems on chordal graphs, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, On \(H\)-topological intersection graphs, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Subexponential-time algorithms for finding large induced sparse subgraphs, Unnamed Item, 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, Vertex Deletion Problems on Chordal Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact exponential algorithms.
- The three-in-a-tree problem
- Monadic second-order evaluations on tree-decomposable graphs
- A linear algorithm for the group path problem on chordal graphs
- Induced packing of odd cycles in planar graphs
- Graph minors. III. Planar tree-width
- Efficient reduction for path problems on circular-arc graphs
- Minimal triangulations of graphs: a survey
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Minimum weight feedback vertex sets in circle graphs
- Finding induced trees
- Graph minors. V. Excluding a planar graph
- The maximum k-colorable subgraph problem for chordal graphs
- The ellipsoid method and its consequences in combinatorial optimization
- On the complexity of testing for odd holes and induced odd paths
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Induced matchings
- A partial k-arboretum of graphs with bounded treewidth
- Quickly excluding a planar graph
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Induced matchings in asteroidal triple-free graphs
- Listing all potential maximal cliques of a graph
- Finding a maximum induced matching in weakly chordal graphs
- New results on induced matchings
- Contraction obstructions for treewidth
- Treewidth computation and extremal combinatorics
- Fast algorithms for max independent set
- The Erdős-Pósa property for long circuits
- Independent packings in structured graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- An Improved Exact Algorithm for Undirected Feedback Vertex Set
- Exact Algorithms for Maximum Independent Set
- MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS
- Exponential time algorithms for the minimum dominating set problem on some graph classes
- Exact Algorithm for the Maximum Induced Planar Subgraph Problem
- Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
- Deciding first-order properties of locally tree-decomposable structures
- The Use of Linear Graphs in Gauss Elimination
- Easy problems for tree-decomposable graphs
- A measure & conquer approach for the analysis of exact algorithms
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- Exact Algorithms for Treewidth and Minimum Fill-In
- The Complexity of the Partial Order Dimension Problem
- Algorithms for maximum independent sets
- On the presence of disjoint subgraphs of a specified type
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Finding a Maximum Independent Set
- Minimum Fill-in on Circle and Circular-Arc Graphs
- Graph Classes: A Survey
- Robust algorithms for restricted domains
- Treewidth and Pathwidth of Permutation Graphs
- Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
- (Meta) Kernelization
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Independent Set in P5-Free Graphs in Polynomial Time
- Subexponential Parameterized Algorithm for Minimum Fill-In
- Bidimensionality and Geometric Graphs
- A Computing Procedure for Quantification Theory
- Exact Computation of Maximum Induced Forest
- On cliques in graphs
