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

DOI10.1016/J.IC.2013.08.007MaRDI QIDQ393084zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh

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

Permutations, words, matrices (05A05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing
• The parameterized complexity of stabbing rectangles
• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• Fixed-parameter tractability and lower bounds for stabbing problems
• The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants

Cites work

• scientific article; zbMATH DE number 434912 (Why is no real title available?)
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 3903967 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 3997796 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• A characterization of perfect graphs
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Algorithmic graph theory and perfect graphs
• An efficient parameterized algorithm for m-set packing
• Approximating minimum cocolorings.
• Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
• Approximation algorithms for hitting objects with straight lines
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Constant approximation algorithms for rectangle stabbing and related problems
• Finding odd cycle transversals.
• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing
• Graph Classes: A Survey
• Improved algorithms for feedback vertex set problems
• On chain and antichain families of a partially ordered set
• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• Parameterized and Exact Computation
• Parametrized complexity theory.
• Partitions of graphs into one or two independent sets and cliques
• Recognizing Berge graphs
• Some extremal results in cochromatic and dichromatic theory
• The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
• The strong perfect graph theorem
• Threshold graphs and related topics

Cited in

(3)

• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing
• Fractional cocoloring of graphs
• Solving partition problems almost always requires pushing many vertices around

This page was built for publication: Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393084)