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

treesringsoptical networkscall schedulingpath coloring

Mathematics Subject Classification ID

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

Related Items

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

• 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