Graph editing to a fixed target

DOI10.1016/J.DAM.2014.07.008zbMATH Open1350.05161OpenAlexW1984546211MaRDI QIDQ344855FDOQ344855

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

Recommendations

• Graph editing to a fixed target
• Editing to a graph of given degrees
• Editing to a graph of given degrees
• 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

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)

Cites Work

• Optimization, approximation, and complexity classes
• On graphs with no induced subdivision of \(K_4\)
• The node-deletion problem for hereditary properties is NP-complete
• Graph minors. XIII: The disjoint paths problem
• Title not available (Why is that?)
• Complexity classification of some edge modification problems
• Contracting graphs to paths and trees
• Finding topological subgraphs is fixed-parameter tractable
• The complexity of induced minors and related problems
• 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
• NP-completeness results for edge modification problems
• 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
• Induced immersions
• Obtaining a bipartite graph by contracting few edges
• Detecting induced subgraphs
• Contracting chordal graphs and bipartite graphs to paths and trees
• Chordless paths through three vertices

Cited In (3)

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

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)