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

DOI10.1016/J.DAM.2005.05.017MaRDI QIDQ2489960zbMATH OpenOpenAlexFDO

Authors Danica Vukadinović Greetham, Thomas Erlebach

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

Edge-disjoint pathsApproximation algorithmMaximum path coloringPath coloringMin-cost flow

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1839474
• The maximum edge-disjoint paths problem in complete graphs
• The complexity of path coloring and call scheduling
• On the maximum disjoint paths problem on edge-colored graphs
• Routing and path multicoloring

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1261807 (Why is no real title available?)
• scientific article; zbMATH DE number 1303573 (Why is no real title available?)
• scientific article; zbMATH DE number 1303779 (Why is no real title available?)
• scientific article; zbMATH DE number 1182769 (Why is no real title available?)
• scientific article; zbMATH DE number 1754632 (Why is no real title available?)
• scientific article; zbMATH DE number 1421019 (Why is no real title available?)
• A Theorem on Coloring the Lines of a Network
• Colouring paths in directed symmetric trees with applications to WDM routing
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Efficient algorithms for interval graphs and circular-arc graphs
• Efficient routing in all-optical networks
• Efficient routing in optical networks
• Geometric algorithms and combinatorial optimization
• Graph-Theoretic Concepts in Computer Science
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Network flows. Theory, algorithms, and applications.
• On the \(k\)-coloring of intervals
• Optimal wavelength routing on directed fiber trees
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Randomized path coloring on binary trees.
• The complexity of path coloring and call scheduling
• The edge intersection graphs of paths in a tree

Cited in

(4)

• Wavelength assignment in multifiber star networks
• scientific article; zbMATH DE number 1839474 (Why is no real title available?)
• The maximum edge-disjoint paths problem in complete graphs
• Multicommodity flow in trees: packing via covering and iterated relaxation

This page was built for publication: Path problems in generalized stars, complete graphs, and brick wall graphs

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