Interval Deletion Is Fixed-Parameter Tractable
From MaRDI portal
Publication:4962179
DOI10.1145/2629595zbMath1398.68220arXiv1211.5933OpenAlexW2003744153MaRDI QIDQ4962179
Publication date: 30 October 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1211.5933
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Paths to Trees and Cacti, Faster FPT algorithms for deletion to pairs of graph classes, Towards constant-factor approximation for chordal/distance-hereditary vertex deletion, Reducing rank of the adjacency matrix by graph modification, Reducing Rank of the Adjacency Matrix by Graph Modification, Distance from triviality 2.0: hybrid parameterizations, An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion, Quick but odd growth of cacti, Erdös-Pósa Property of Obstructions to Interval Graphs, Approximation and Kernelization for Chordal Vertex Deletion, Parameterized complexity of perfectly matched sets, Polynomial Kernel for Interval Vertex Deletion, Erdős–Pósa property of obstructions to interval graphs, Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes, Deletion to scattered graph classes. I: Case of finite number of graph classes, A survey of parameterized algorithms and the complexity of edge modification, Unnamed Item, Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams, Unnamed Item, Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes, Paths to trees and cacti, Rank reduction of oriented graphs by vertex and edge deletions, Conflict free version of covering problems on graphs: classical and parameterized, Subexponential parameterized algorithms and kernelization on almost chordal graphs, The parameterized complexity of cycle packing: indifference is not an issue, Unnamed Item, On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
