On the Power of Advice and Randomization for the Disjoint Path Allocation Problem

DOI10.1007/978-3-319-04298-5_9zbMath1432.68009OpenAlexW1500430341MaRDI QIDQ2938097

Sacha Krug, Kfir Barhum, Heidi Gebauer, Björn Steffen, Michal Forišek, Jasmin Smula, Juraj Hromkovič, Hans-Joachim Böckenhauer

Publication date: 13 January 2015

Published in: SOFSEM 2014: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/182199

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (19)

Call admission problems on grids with advice ⋮ Online Multi-Coloring with Advice ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ Disjoint Path Allocation with Sublinear Advice ⋮ On Energy-Efficient Computations With Advice ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ Call admission problems on trees ⋮ Advice complexity of online non-crossing matching ⋮ Advice complexity of disjoint path allocation ⋮ The advice complexity of a class of hard online problems ⋮ Fully Online Matching with Advice on General Bipartite Graphs and Paths ⋮ Length-Weighted Disjoint Path Allocation ⋮ Online interval scheduling with predictions ⋮ On the advice complexity of the online dominating set problem ⋮ Online algorithms with advice: the tape model ⋮ Online Minimum Spanning Tree with Advice ⋮ Advice Complexity of the Online Search Problem ⋮ Towards using the history in online computation with advice ⋮ Online multi-coloring with advice

This page was built for publication: On the Power of Advice and Randomization for the Disjoint Path Allocation Problem