Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing

DOI10.1137/S009753979833965XzbMath1112.68134OpenAlexW2081320476MaRDI QIDQ3434990

Amos Fiat, Yair Bartal, Stefano Leonardi

Publication date: 3 May 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753979833965x

zbMATH Keywords

competitive analysislower boundsrandomized algorithmsnetwork optimizationon-line computationgraph problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Communication networks in operations research (90B18) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (4)

Online covering with \(\ell_q\)-norm objectives and applications to network design ⋮ Online coloring a token graph ⋮ On-line routing in all-optical networks ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs

This page was built for publication: Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing