Conversion of coloring algorithms into maximum weight independent set algorithms

DOI10.1016/j.dam.2004.11.007zbMath1087.68069OpenAlexW1969310934MaRDI QIDQ1775063

Klaus Jansen, Erlebach, Thomas

Publication date: 4 May 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.11.007

zbMATH Keywords

Linear programmingApproximation algorithmsEdge-disjoint pathsPath coloringTime-constrained packet schedulingWeighted independent set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Edge and vertex intersection of paths in a tree
• Decomposition by clique separators
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The ellipsoid method and its consequences in combinatorial optimization
• Optimization, approximation, and complexity classes
• Geometric algorithms and combinatorial optimization
• On the ratio of optimal integral and fractional covers
• Zero knowledge and the chromatic number
• Multi-phase algorithms for throughput maximization for real-time scheduling
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Optimal wavelength routing on directed fiber trees
• The Maximum Edge-Disjoint Paths Problem in Bidirected Trees
• Approximating the Throughput of Multiple Machines in Real-Time Scheduling
• The Complexity of Coloring Circular Arcs and Chords
• Coloring a Family of Circular Arcs
• Maximum weighted independent sets on transitive graphs and applications
• On the hardness of approximating minimization problems
• On approximation properties of the Independent set problem for degree 3 graphs
• Implementation of approximation algorithms for weighted and unweighted edge-disjoint paths in bidirected trees
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• A unified approach to approximating resource allocation and scheduling

This page was built for publication: Conversion of coloring algorithms into maximum weight independent set algorithms