Chordal deletion is fixed-parameter tractable
From MaRDI portal
Publication:973007
DOI10.1007/s00453-008-9233-8zbMath1220.05066MaRDI QIDQ973007
Publication date: 28 May 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9233-8
05C38: Paths and cycles
Related Items
Chordal editing is fixed-parameter tractable, Satisfiability of acyclic and almost acyclic CNF formulas, Parameterized complexity of vertex deletion into perfect graph classes, Parameterized complexity of three edge contraction problems with degree constraints, Unit interval editing is fixed-parameter tractable, Parameterized complexity of finding connected induced subgraphs, Proper interval vertex deletion, Modifying a graph using vertex elimination, Faster parameterized algorithms for deletion to split graphs, Obtaining a planar graph by vertex deletion, Contracting graphs to paths and trees, Parameterized complexity of Eulerian deletion problems, A faster FPT algorithm for bipartite contraction, Open Problems on Graph Coloring for Special Graph Classes, Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques, Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs, Graph Minors and Parameterized Algorithm Design, Measuring Indifference: Unit Interval Vertex Deletion, Proper Interval Vertex Deletion, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, Parameterized Complexity of Eulerian Deletion Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding odd cycle transversals.
- Parameterized coloring problems on chordal graphs
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- The node-deletion problem for hereditary properties is NP-complete
- Treewidth. Computations and approximations
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Parameterized complexity of vertex colouring
- Computing crossing numbers in quadratic time
- Graph minors. XIII: The disjoint paths problem
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
- Wheel-Free Deletion Is W[2-Hard]
- Obtaining a Planar Graph by Vertex Deletion
- Computing the Minimum Fill-In is NP-Complete
- Algorithmic Aspects of Vertex Elimination on Graphs
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Detecting a Network Failure
- Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
- Complexity classification of some edge modification problems
