Proper interval vertex deletion

DOI10.1007/s00453-012-9661-3zbMath1262.68052OpenAlexW2131274579MaRDI QIDQ1949742

Yngve Villanger, Pim van 't Hof

Publication date: 16 May 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9661-3

zbMATH Keywords

proper interval graphsvertex deletionFPT algorithmsproper circular arc graphs

Mathematics Subject Classification ID

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

Related Items

Vertex deletion into bipartite permutation graphs, An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion, Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes, Sublinear approximation algorithms for boxicity and related problems, A survey of parameterized algorithms and the complexity of edge modification, Contracting graphs to paths and trees, A faster FPT algorithm for bipartite contraction, Faster algorithms for vertex partitioning problems parameterized by clique-width, Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes, Unnamed Item, Unit interval vertex deletion: fewer vertices are relevant, Unit interval editing is fixed-parameter tractable, Vertex deletion into bipartite permutation graphs, Declawing a graph: polyhedra and branch-and-cut algorithms, Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results, The parameterized complexity of cycle packing: indifference is not an issue, Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved upper bounds for vertex cover
• Chordal deletion is fixed-parameter tractable
• The node-deletion problem for hereditary properties is NP-complete
• Call routing and the ratcatcher
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On linear and circular structure of (claw, net)-free graphs
• Obtaining a planar graph by vertex deletion
• Structure theorems for some circular-arc graphs
• Measuring Indifference: Unit Interval Vertex Deletion
• Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
• Representation of a finite graph by a set of intervals on the real line
• Wheel-Free Deletion Is W[2-Hard]
• On Feedback Vertex Set New Measure and New Structures
• Interval Completion Is Fixed Parameter Tractable
• Edge-Deletion Problems
• Computing the Minimum Fill-In is NP-Complete
• Graph Classes: A Survey
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph