Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
From MaRDI portal
Publication:393084
DOI10.1016/j.ic.2013.08.007zbMath1358.68313MaRDI QIDQ393084
Venkatesh Raman, Saket Saurabh, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov
Publication date: 16 January 2014
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2013.08.007
68Q25: Analysis of algorithms and problem complexity
68W05: Nonnumerical algorithms
05A05: Permutations, words, matrices
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around, Fractional cocoloring of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding odd cycle transversals.
- The strong perfect graph theorem
- Constant approximation algorithms for rectangle stabbing and related problems
- Improved algorithms for feedback vertex set problems
- On chain and antichain families of a partially ordered set
- Approximation algorithms for hitting objects with straight lines
- Approximating minimum cocolorings.
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- Partitions of graphs into one or two independent sets and cliques
- Parametrized complexity theory.
- Recognizing Berge graphs
- A characterization of perfect graphs
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- A fixed-parameter algorithm for the directed feedback vertex set problem
- The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
- Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing
- Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
- Some extremal results in cochromatic and dichromatic theory
- Graph Classes: A Survey
- An efficient parameterized algorithm for m-set packing
- Parameterized and Exact Computation
- Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems