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

zbMATH Keywords

complexityvertex partitionscomplete partitions

Mathematics Subject Classification ID

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)

Approximability of Packing Disjoint Cycles ⋮ Approximability of packing disjoint cycles

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