A better performance guarantee for approximate graph coloring

DOI10.1007/BF01840398zbMATH Open0697.68032MaRDI QIDQ911757FDOQ911757

Authors: Bonnie Berger, John Rompel 

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

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

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)

Cites Work

• Improving the performance guarantee for approximate graph coloring
• The Complexity of Near-Optimal Graph Coloring
• Title not available (Why is that?)

Cited In (14)

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

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)