Proper interval vertex deletion
From MaRDI portal
Publication:1949742
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
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
