Linear Recognition of Almost Interval Graphs

DOI10.1137/1.9781611974331.ch77zbMath1410.68284arXiv1403.1515OpenAlexW1924811958MaRDI QIDQ4575657

Yixin Cao

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.1515

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (24)

Paths to Trees and Cacti ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Vertex deletion into bipartite permutation graphs ⋮ Erdös-Pósa Property of Obstructions to Interval Graphs ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ 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 ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ Unit interval editing is fixed-parameter tractable ⋮ Paths to trees and cacti ⋮ Slightly Superexponential Parameterized Problems ⋮ Vertex deletion into bipartite permutation graphs ⋮ Rank reduction of oriented graphs by vertex and edge deletions ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Vertex deletion problems on chordal graphs ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ Parameterized complexity of diameter ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs ⋮ Vertex Deletion Problems on Chordal Graphs

This page was built for publication: Linear Recognition of Almost Interval Graphs