Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization

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

Mathematics Subject Classification ID

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