Fractional path coloring in bounded degree trees with applications
DOI10.1007/S00453-009-9278-3zbMATH Open1297.05079OpenAlexW2129708018MaRDI QIDQ5961980FDOQ5961980
Hervé Rivano, Afonso G. Ferreira, C. Kaklamanis, I. 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
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 \(\mathcal Q\)-edge-coloring of graphs
- scientific article; zbMATH DE number 1754632
- Fractional DP-colorings of sparse graphs
approximation algorithmsfractional coloringlinear relaxationoptical networkswavelength division multiplexingpath coloringfixed parameter tractable problem
Linear programming (90C05) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Decomposition by clique separators
- The ellipsoid method and its consequences in combinatorial optimization
- On the ratio of optimal integral and fractional covers
- Geometric algorithms and combinatorial optimization.
- The edge intersection graphs of paths in a tree
- Weighted sums of certain dependent random variables
- Title not available (Why is that?)
- Zero knowledge and the chromatic number
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Coloring a Family of Circular Arcs
- Optimal wavelength routing on directed fiber trees
- The round-up property of the fractional chromatic number for proper circular arc graphs
- Title not available (Why is that?)
- Colouring paths in directed symmetric trees with applications to WDM routing
- STACS 2004
- Title not available (Why is that?)
- Approximation Algorithms for Path Coloring in Trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation and Online Algorithms
Cited In (2)
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)
