Graph editing to a fixed target

DOI10.1016/J.DAM.2014.07.008MaRDI QIDQ344855zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Daniël Paulusma, Iain 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

zbMATH Keywords

computational complexitygraph containment relationgraph editing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Graph editing to a fixed target
• Editing to Eulerian graphs
• Editing to Eulerian graphs
• Graph editing to a given degree sequence
• Graph editing to a given degree sequence
• Editing the simplest graphs
• Editing to a connected graph of given degrees
• Editing to a connected graph of given degrees

Cites work

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Chordless paths through three vertices
• Complexity classification of some edge modification problems
• Contracting chordal graphs and bipartite graphs to paths and trees
• Detecting fixed patterns in chordal graphs in polynomial time
• Detecting induced minors in AT-free graphs
• Detecting induced star-like minors in polynomial time
• Finding topological subgraphs is fixed-parameter tractable
• Graph minors. XIII: The disjoint paths problem
• Increasing the minimum degree of a graph by contractions
• Induced immersions
• NP-completeness results for edge modification problems
• Obtaining a bipartite graph by contracting few edges
• Obtaining planarity by contracting few edges
• On graph contractions and induced minors
• On graphs with no induced subdivision of \(K_4\)
• Optimization, approximation, and complexity classes
• The complexity of induced minors and related problems
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(3)

• Reconfiguration of graph minors
• Graph editing to a fixed target
• Chordal editing is fixed-parameter tractable

This page was built for publication: Graph editing to a fixed target

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344855)