Path problems in generalized stars, complete graphs, and brick wall graphs

DOI10.1016/j.dam.2005.05.017zbMath1090.68082OpenAlexW2073800226MaRDI QIDQ2489960

Danica Vukadinović Greetham, Erlebach, Thomas

Publication date: 28 April 2006

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

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

zbMATH Keywords

Approximation algorithmEdge-disjoint pathsMaximum path coloringPath coloringMin-cost flow

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Wavelength assignment in multifiber star networks

Cites Work

• Primal-dual approximation algorithms for integral flow and multicut in trees
• The edge intersection graphs of paths in a tree
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Geometric algorithms and combinatorial optimization
• Randomized path coloring on binary trees.
• On the \(k\)-coloring of intervals
• Optimal wavelength routing on directed fiber trees
• Efficient routing in all-optical networks
• Efficient algorithms for interval graphs and circular-arc graphs
• Efficient routing in optical networks
• Colouring paths in directed symmetric trees with applications to WDM routing
• A Theorem on Coloring the Lines of a Network
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Graph-Theoretic Concepts in Computer Science
• The complexity of path coloring and call scheduling
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item