Modifying a graph using vertex elimination
From MaRDI portal
Publication:2345941
DOI10.1007/s00453-013-9848-2zbMath1314.68232OpenAlexW2082278277MaRDI QIDQ2345941
Michał Pilipczuk, Pinar Heggernes, Fredrik Manne, Daniël Paulusma, Pim van 't Hof, Petr A. Golovach
Publication date: 21 May 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/14116/1/14116.pdf
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph operations (line graphs, products, etc.) (05C76)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dominating set is fixed parameter tractable in claw-free graphs
- Minimal triangulations of graphs: a survey
- Chordal deletion is fixed-parameter tractable
- On problems without polynomial kernels
- Quickly excluding a planar graph
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Obtaining a planar graph by vertex deletion
- A Quartic Kernel for Pathwidth-One Vertex Deletion
- Measuring Indifference: Unit Interval Vertex Deletion
- Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
- The Use of Linear Graphs in Gauss Elimination
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Spanning Trees with Many Leaves
- Edge-Deletion Problems
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Algorithmic Aspects of Vertex Elimination on Graphs
- How to Eliminate a Graph
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Complexity classification of some edge modification problems
