Path multicoloring with fewer colors in spiders and caterpillars

DOI10.1007/s00607-007-0234-2zbMath1130.68082OpenAlexW2064072089MaRDI QIDQ2460919

Katerina Potika, Stathis Zachos, Aris Pagourtzis

Publication date: 19 November 2007

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-007-0234-2

zbMATH Keywords

approximation algorithmspath coloringspiderscaterpillarsmultifiber all-optical networks

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Stathis Zachos at 70! ⋮ Path multicoloring in spider graphs with even color multiplicity ⋮ Wavelength assignment in multifiber star networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The edge intersection graphs of paths in a tree
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Routing and path multicoloring
• Optimal wavelength routing on directed fiber trees
• Routing and wavelength assignment in multifiber WDM networks with non-uniform fiber cost
• Efficient routing in all-optical networks
• On the $1.1$ Edge-Coloring of Multigraphs
• The NP-Completeness of Some Edge-Partition Problems
• Automata, Languages and Programming
• Graph-Theoretic Concepts in Computer Science
• The complexity of path coloring and call scheduling

This page was built for publication: Path multicoloring with fewer colors in spiders and caterpillars