Fractional path coloring in bounded degree trees with applications

DOI10.1007/s00453-009-9278-3zbMath1297.05079OpenAlexW2129708018MaRDI QIDQ5961980

Herve Rivano, Afonso G. Ferreira, Christos Kaklamanis, Ioannis Caragiannis, Stéphane Pérennes

Publication date: 16 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9278-3

zbMATH Keywords

optical networksapproximation algorithmspath coloringlinear relaxationfixed parameter tractable problemfractional coloringwavelength division multiplexing

Mathematics Subject Classification ID

Linear programming (90C05) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The edge intersection graphs of paths in a tree
• Decomposition by clique separators
• The ellipsoid method and its consequences in combinatorial optimization
• On the ratio of optimal integral and fractional covers
• Zero knowledge and the chromatic number
• Geometric algorithms and combinatorial optimization.
• Optimal wavelength routing on directed fiber trees
• Weighted sums of certain dependent random variables
• Coloring a Family of Circular Arcs
• Colouring paths in directed symmetric trees with applications to WDM routing
• The round-up property of the fractional chromatic number for proper circular arc graphs
• STACS 2004
• Approximation Algorithms for Path Coloring in Trees
• Approximation and Online Algorithms

This page was built for publication: Fractional path coloring in bounded degree trees with applications