Fractional path coloring in bounded degree trees with applications

DOI10.1007/S00453-009-9278-3MaRDI QIDQ5961980zbMATH OpenOpenAlexFDO

Authors I. Caragiannis, Afonso G. Ferreira, C. Kaklamanis, Stéphane Pérennes, Hervé Rivano

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

approximation algorithmsfractional coloringlinear relaxationoptical networkswavelength division multiplexingpath coloringfixed parameter tractable problem

Mathematics Subject Classification ID

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

Recommendations

• Approximation and Online Algorithms
• Paths between colourings of graphs with bounded tree-width
• Fractional coloring methods with applications to degenerate graphs and graphs on surfaces
• Fractional coloring of triangle-free planar graphs
• Generalized fractional total colorings of graphs
• Borel fractional colorings of Schreier graphs
• Approximation Algorithms for Path Coloring in Trees
• Fractional Q-edge-coloring of graphs
• scientific article; zbMATH DE number 1754632
• Fractional DP-colorings of sparse graphs

Cites work

• scientific article; zbMATH DE number 1670530 (Why is no real title available?)
• scientific article; zbMATH DE number 3706474 (Why is no real title available?)
• scientific article; zbMATH DE number 1182769 (Why is no real title available?)
• scientific article; zbMATH DE number 2086377 (Why is no real title available?)
• scientific article; zbMATH DE number 2102779 (Why is no real title available?)
• Approximation Algorithms for Path Coloring in Trees
• Approximation algorithms for NP-hard problems.
• Approximation and Online Algorithms
• Coloring a Family of Circular Arcs
• Colouring paths in directed symmetric trees with applications to WDM routing
• Decomposition by clique separators
• Geometric algorithms and combinatorial optimization.
• Graph theory
• On the ratio of optimal integral and fractional covers
• Optimal wavelength routing on directed fiber trees
• Primal-dual approximation algorithms for integral flow and multicut in trees
• STACS 2004
• The edge intersection graphs of paths in a tree
• The ellipsoid method and its consequences in combinatorial optimization
• The round-up property of the fractional chromatic number for proper circular arc graphs
• Weighted sums of certain dependent random variables
• Zero knowledge and the chromatic number

Cited in

(5)

• Parameterized maximum path coloring
• scientific article; zbMATH DE number 1754632 (Why is no real title available?)
• Parameterized maximum path coloring
• 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

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