The complexity of path coloring and call scheduling
From MaRDI portal
Publication:5941061
DOI10.1016/S0304-3975(99)00152-8zbMath0974.68021WikidataQ56390647 ScholiaQ56390647MaRDI QIDQ5941061
Erlebach, Thomas, Klaus Jansen
Publication date: 20 August 2001
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (26)
Routing and wavelength assignment by partition colouring ⋮ On the minimum and maximum selective graph coloring problems in some graph classes ⋮ Parameterized Maximum Path Coloring ⋮ Lagrangean decomposition/relaxation for the routing and wavelength assignment problem ⋮ Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem ⋮ On some applications of the selective graph coloring problem ⋮ A biased random-key genetic algorithm to maximize the number of accepted lightpaths in WDM optical networks ⋮ Minimum multiplicity edge coloring via orientation ⋮ Approximating call-scheduling makespan in all-optical networks ⋮ Parameterized maximum path coloring ⋮ A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree ⋮ Dual-neighborhood iterated local search for routing and wavelength assignment ⋮ Path multicoloring in spider graphs with even color multiplicity ⋮ A Markov chain on the solution space of edge colorings of bipartite graphs ⋮ Inapproximability and approximability of minimal tree routing and coloring ⋮ Path multicoloring with fewer colors in spiders and caterpillars ⋮ Routing permutations and involutions on optical ring networks: Complexity results and solution to an open problem ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Path problems in generalized stars, complete graphs, and brick wall graphs ⋮ Short length Menger's theorem and reliable optical routing ⋮ Multiflows in symmetric digraphs ⋮ Wavelength assignment in multifiber star networks ⋮ Efficient algorithms for wavelength assignment on trees of rings ⋮ Colouring graphs with no induced six-vertex path or diamond ⋮ Nash equilibria in all-optical networks ⋮ A biased random-key genetic algorithm for routing and wavelength assignment under a sliding scheduled traffic model
Cites Work
- A note on optical routing on trees
- The edge intersection graphs of paths in a tree
- Decomposition by clique separators
- Complexity of scheduling multiprocessor tasks with prespecified processors allocations
- On-line routing in all-optical networks
- On the complexity of the disjoint paths problem
- Efficient routing in all-optical networks
- On the $1.1$ Edge-Coloring of Multigraphs
- Scheduling File Transfers
- Scheduling Multiprocessor Tasks to Minimize Schedule Length
- The NP-Completeness of Edge-Coloring
- Efficient algorithms for interval graphs and circular-arc graphs
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- The Complexity of Coloring Circular Arcs and Chords
- Coloring a Family of Circular Arcs
- Efficient routing in optical networks
- Constrained bipartite edge coloring with applications to wavelength routing
- Colouring paths in directed symmetric trees with applications to WDM routing
- Efficient wavelength routing on directed fiber trees
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The complexity of path coloring and call scheduling
