Chordal editing is fixed-parameter tractable

DOI10.4230/LIPICS.STACS.2014.214MaRDI QIDQ2965485zbMATH OpenOpenAlexFDO

Authors Yixin Cao, Dániel Marx

Publication date 3 March 2017

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2014/4459/pdf/17.pdf/

zbMATH Keywords

holeschordal completionchordal deletionchordal graphclique tree decompositiongraph modification problemsparameterized computationsimplic

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Chordal editing is fixed-parameter tractable
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Cograph editing: complexity and parameterized algorithms
• Chordal deletion is fixed-parameter tractable
• Chordal Deletion Is Fixed-Parameter Tractable

Cited in

(12)

• On the effectiveness of the incremental approach to minimal chordal edge modification
• Modification to Planarity is Fixed Parameter Tractable
• Edge deletion problems: branching facilitated by modular decomposition
• Reducing rank of the adjacency matrix by graph modification
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Chordal editing is fixed-parameter tractable
• Paths to trees and cacti
• Vertex deletion problems on chordal graphs
• Vertex deletion problems on chordal graphs
• Reducing rank of the adjacency matrix by graph modification
• Graph editing to a fixed target
• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques

This page was built for publication: Chordal editing is fixed-parameter tractable

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