Priority algorithms with advice for disjoint path allocation problems

DOI10.1016/J.TCS.2024.114942MaRDI QIDQ6639746FDOQ6639746

Authors: Hans-Joachim Böckenhauer, Fabian Frei, Silvan Horvath 

Publication date: 18 November 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Recommendations

• Advice complexity of disjoint path allocation
• Disjoint path allocation with sublinear advice
• On the power of advice and randomization for the disjoint path allocation problem

zbMATH Keywords

advice complexitygreedy algorithmspriority algorithmsdisjoint path allocation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Title not available (Why is that?)
• Note on scheduling intervals on-line
• On the \(k\)-coloring of intervals
• Information complexity of online problems
• Online computation with advice
• (Incremental) priority algorithms
• The power of priority algorithms for facility location and set cover
• How Much Information about the Future Is Needed?
• The string guessing problem as a method to prove lower bounds on the advice complexity
• Priority algorithms for graph optimization problems
• Bounds on greedy algorithms for MAX SAT
• On the power of advice and randomization for the disjoint path allocation problem
• Online algorithms with advice: the tape model
• Sur l'extension de l'ordre partiel.
• Call admission problems on grids with advice
• Call admission problems on trees
• Length-Weighted Disjoint Path Allocation

This page was built for publication: Priority algorithms with advice for disjoint path allocation problems

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