Approximating circular arc colouring and bandwidth allocation in all-optical ring networks

DOI10.1007/BFB0053971MaRDI QIDQ4400852zbMATH OpenFDO

Authors V. Kumar

Publication date 10 December 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0053971

zbMATH Keywords

bandwidth allocationcircular arc graph colouring problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Combinatorial probability (60C05) Graph theory (including graph drawing) in computer science (68R10) Linear programming (90C05)

Recommendations

• An approximation algorithm for circular arc colouring
• STACS 2004
• Wavelength allocation on trees of rings
• Routing and path multicoloring

Cited in

(13)

• Nash equilibria in all-optical networks
• On the computational complexity of strong edge coloring
• Splittable traffic partition in WDM/SONET rings to minimize SONET ADMs
• Randomized path coloring on binary trees.
• On packing and coloring hyperedges in a cycle
• Path problems in generalized stars, complete graphs, and brick wall graphs
• Minimizing maximum fiber requirement in optical networks
• Revisiting Tucker's algorithm to color circular-arc graphs
• Interval scheduling: A survey
• Line system design and a generalized coloring problem
• The complexity of path coloring and call scheduling
• An approximation algorithm for circular arc colouring
• Fractional path coloring in bounded degree trees with applications

This page was built for publication: Approximating circular arc colouring and bandwidth allocation in all-optical ring networks

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