A better performance guarantee for approximate graph coloring
From MaRDI portal
Publication:911757
DOI10.1007/BF01840398zbMath0697.68032MaRDI QIDQ911757
Publication date: 1990
Published in: Algorithmica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (9)
Periodic assignment and graph colouring ⋮ On the Complexity of Scheduling to Optimize Average Response Time ⋮ Mutual exclusion scheduling ⋮ Approximating the independence number via the \(\vartheta\)-function ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Approximating maximum independent sets by excluding subgraphs ⋮ A still better performance guarantee for approximate graph coloring ⋮ Approximating maximum independent sets by excluding subgraphs ⋮ The allocation problem in hardware design
Cites Work
This page was built for publication: A better performance guarantee for approximate graph coloring
