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

DOI10.1016/J.DAM.2005.05.017zbMATH Open1090.68082OpenAlexW2073800226MaRDI QIDQ2489960FDOQ2489960

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

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

zbMATH Keywords

Edge-disjoint pathsApproximation algorithmMaximum path coloringPath coloringMin-cost flow

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Wavelength assignment in multifiber star networks
• Title not available (Why is that?)
• 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)