Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems

DOI10.1007/978-3-031-34347-6_6arXiv2303.17346OpenAlexW4379134737MaRDI QIDQ6182892

Henri Lotze, Niklas Berndt

Publication date: 22 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2303.17346

zbMATH Keywords

online algorithmsadvice complexitygraph modificationedge-deletionnode-deletionlate accept model

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Online algorithms with advice: the tape model
• The advice complexity of a class of hard online problems
• Online node- and edge-deletion problems with advice
• On the advice complexity of the \(k\)-server problem
• Information Complexity of Online Problems
• Competitive Caching with Machine Learned Advice
• Measuring the problem-relevant information in input
• Online Dominating Set
• Relaxing the irrevocability requirement for online graph algorithms

This page was built for publication: Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems