The complexity of path coloring and call scheduling

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)

zbMATH Keywords

trees; rings; optical networks; call scheduling; path coloring

Mathematics Subject Classification ID

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

Colouring graphs with no induced six-vertex path or diamond, Dual-neighborhood iterated local search for routing and wavelength assignment, On the minimum and maximum selective graph coloring problems in some graph classes, Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem, A biased random-key genetic algorithm to maximize the number of accepted lightpaths in WDM optical networks, Parameterized maximum path coloring, A constant factor approximation algorithm for the storage allocation problem, Short length Menger's theorem and reliable optical routing, Multiflows in symmetric digraphs, A biased random-key genetic algorithm for routing and wavelength assignment under a sliding scheduled traffic model, Routing and wavelength assignment by partition colouring, Approximating call-scheduling makespan in all-optical networks, Inapproximability and approximability of minimal tree routing and coloring, Efficient algorithms for wavelength assignment on trees of rings, Nash equilibria in all-optical networks, Minimum multiplicity edge coloring via orientation, Path multicoloring in spider graphs with even color multiplicity, A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree, 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, Path problems in generalized stars, complete graphs, and brick wall graphs, On some applications of the selective graph coloring problem, A Markov chain on the solution space of edge colorings of bipartite graphs, Parameterized Maximum Path Coloring, Lagrangean decomposition/relaxation for the routing and wavelength assignment problem, Wavelength assignment in multifiber star networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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