Online node- and edge-deletion problems with advice

DOI10.1007/S00453-021-00840-9MaRDI QIDQ1979452zbMATH OpenOpenAlexFDO

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

Publication date 2 September 2021

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

advice complexitydelayed decision modeledge-deletiongraph modificationnode-deletiononline algorithm

Mathematics Subject Classification ID

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

Recommendations

• Further results on online node- and edge-deletion problems with advice
• On the Advice Complexity of Online Edge- and Node-Deletion Problems
• Advice complexity of the online induced subgraph problem
• Advice complexity for a class of online problems
• The advice complexity of a class of hard online problems

Cites work

• Advice complexity of the online induced subgraph problem
• Distance-hereditary graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Further results on online node- and edge-deletion problems with advice
• scientific article; zbMATH DE number 193017 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• Information complexity of online problems
• Mathematics for the Analysis of Algorithms.
• 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
• On the Advice Complexity of Online Problems
• On the advice complexity of the k-server problem
• On the advice complexity of the knapsack problem
• On the power of randomness versus advice in online computation
• On-line vertex-covering
• Online algorithms with advice: the tape model
• Online computation with advice
• The Comparability Graph of a Tree
• The online knapsack problem: advice and randomization

Cited in

(7)

• Further results on online node- and edge-deletion problems with advice
• On the Advice Complexity of Online Edge- and Node-Deletion Problems
• Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems
• Online knapsack with removal and recourse
• Delaying decisions and reservation costs
• Online knapsack with removal and recourse
• Online unbounded knapsack

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

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