Complete partitions of graphs
DOI10.1007/s00493-007-2169-9zbMath1164.68038OpenAlexW3138200510MaRDI QIDQ949754
Jaikumar Radhakrishnan, Magnús M. Halldórsson, Sivaramakrishnan Sivasubramanian, Guy Kortsarz
Publication date: 21 October 2008
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-007-2169-9
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the minimum maximal independence number
- Hadwiger's conjecture is true for almost every graph
- Partition graphs and coloring numbers of a graph
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- The complexity of harmonious colouring for trees
- Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi
- The achromatic number of bounded degree trees
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Achromatic number is NP-complete for cographs and interval graphs
- On Approximating the Achromatic Number
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Asymmetric k-center is log * n -hard to approximate
- Polylogarithmic inapproximability
- Achromatic numbers of random graphs
- On the pseudoachromatic number of a graph
- On the hardness of approximating minimization problems
- A Parallel Repetition Theorem
- On the pseudoachromatic number of join of graphs
- Balls and bins: A study in negative dependence
- Approximating theDomatic Number
- Some optimal inapproximability results
- Algorithms - ESA 2003
- On the hardness of approximating spanners
This page was built for publication: Complete partitions of graphs
