Chordal editing is fixed-parameter tractable

DOI10.4230/LIPICS.STACS.2014.214zbMATH Open1359.05119OpenAlexW2277578521MaRDI QIDQ2965485FDOQ2965485

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/

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

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)

Cited In (12)

• Modification to Planarity is Fixed Parameter Tractable
• On the effectiveness of the incremental approach to minimal chordal edge modification
• 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
• Paths to trees and cacti
• Chordal editing is fixed-parameter tractable
• Vertex deletion problems on chordal graphs
• Vertex deletion problems on chordal graphs
• Graph editing to a fixed target
• Reducing rank of the adjacency matrix by graph modification
• 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)