Graph editing to a fixed target
From MaRDI portal
Publication:344855
DOI10.1016/j.dam.2014.07.008zbMath1350.05161OpenAlexW1984546211MaRDI QIDQ344855
Petr A. Golovach, Daniël Paulusma, Iain A. Stewart
Publication date: 24 November 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.07.008
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Increasing the minimum degree of a graph by contractions
- Detecting induced minors in AT-free graphs
- A linear time algorithm for the induced disjoint paths problem in planar graphs
- On graph contractions and induced minors
- On graphs with no induced subdivision of \(K_4\)
- Chordless paths through three vertices
- The node-deletion problem for hereditary properties is NP-complete
- Optimization, approximation, and complexity classes
- The complexity of induced minors and related problems
- Graph minors. XIII: The disjoint paths problem
- Obtaining planarity by contracting few edges
- Induced disjoint paths in AT-free graphs
- Detecting fixed patterns in chordal graphs in polynomial time
- Detecting induced star-like minors in polynomial time
- Contracting graphs to paths and trees
- NP-completeness results for edge modification problems
- Induced Immersions
- Obtaining a Bipartite Graph by Contracting Few Edges
- Finding topological subgraphs is fixed-parameter tractable
- Detecting induced subgraphs
- Contracting chordal graphs and bipartite graphs to paths and trees
- Complexity classification of some edge modification problems
This page was built for publication: Graph editing to a fixed target
