Online node- and edge-deletion problems with advice

DOI10.1007/s00453-021-00840-9OpenAlexW3174973330MaRDI QIDQ1979452

Henri Lotze, Peter Rossmanith, Ling-Ju Hung, Li-Hsuan Chen

Publication date: 2 September 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00840-9

zbMATH Keywords

online algorithmadvice complexitygraph modificationedge-deletiondelayed decision modelnode-deletion

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (2)

Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems ⋮ Online knapsack with removal and recourse

Cites Work

• Unnamed Item
• Unnamed Item
• Online algorithms with advice: the tape model
• Online computation with advice
• Mathematics for the Analysis of Algorithms.
• Distance-hereditary graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On-line vertex-covering
• The online knapsack problem: advice and randomization
• On the Advice Complexity of the Knapsack Problem
• On the Advice Complexity of the k-Server Problem
• On the Power of Randomness versus Advice in Online Computation
• Information Complexity of Online Problems
• On the Advice Complexity of Online Problems
• The Comparability Graph of a Tree
• Advice Complexity of the Online Induced Subgraph Problem
• Further Results on Online Node- and Edge-Deletion Problems with Advice
• Measuring the problem-relevant information in input
• Node-and edge-deletion NP-complete problems
• On the Advice Complexity of Online Edge- and Node-Deletion Problems

This page was built for publication: Online node- and edge-deletion problems with advice