A better performance guarantee for approximate graph coloring

DOI10.1007/BF01840398MaRDI QIDQ911757zbMATH OpenFDO

Authors Bonnie Berger, John Rompel

Publication date 1990

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsgraph coloringperformance guarantee

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Improving the performance guarantee for approximate graph coloring
• New approximation guarantee for chromatic number
• New approximation algorithms for graph coloring
• Parallel and On-Line Graph Coloring
• A note on the approximation ratio of graph-coloring

Cites work

• scientific article; zbMATH DE number 3482375 (Why is no real title available?)
• Improving the performance guarantee for approximate graph coloring
• The Complexity of Near-Optimal Graph Coloring

Cited in

(14)

• A still better performance guarantee for approximate graph coloring
• Periodic assignment and graph colouring
• Approximating maximum independent sets by excluding subgraphs
• Approximating maximum independent sets by excluding subgraphs
• scientific article; zbMATH DE number 3854439 (Why is no real title available?)
• Polynomial approximation and graph-coloring
• Approximating the independence number via the \(\vartheta\)-function
• Robust Factorizations and Colorings of Tensor Graphs
• The allocation problem in hardware design
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Improving the performance guarantee for approximate graph coloring
• Mutual exclusion scheduling
• A note on the approximation ratio of graph-coloring
• On the Complexity of Scheduling to Optimize Average Response Time

This page was built for publication: A better performance guarantee for approximate graph coloring

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