Priority algorithms with advice for disjoint path allocation problems

DOI10.1016/J.TCS.2024.114942MaRDI QIDQ6639746zbMATH OpenFDO

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

Publication date 18 November 2024

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

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)

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

Cites work

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

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)