1. Online Node- and Edge-Deletion Problems with Advice.
- Author
-
Chen, Li-Hsuan, Hung, Ling-Ju, Lotze, Henri, and Rossmanith, Peter
- Subjects
- *
ONLINE algorithms , *ADVICE , *GRAPH connectivity , *ALGORITHMS , *SUBGRAPHS - Abstract
In online edge- and node-deletion problems the input arrives node by node and an algorithm has to delete nodes or edges in order to keep the input graph in a given graph class Π at all times. We consider only hereditary properties Π , for which optimal online algorithms exist and which can be characterized by a set of forbidden subgraphs F and analyze the advice complexity of getting an optimal solution. We give almost tight bounds on the Delayed Connected F -Node-Deletion Problem, where all graphs of the family F have to be connected and almost tight lower and upper bounds for the Delayed H -Node-Deletion Problem, where there is one forbidden induced subgraph H that may be connected or not. For the Delayed H -Node-Deletion Problem the advice complexity is basically an easy function of the size of the biggest component in H. Additionally, we give tight bounds on the Delayed Connected F -Edge-Deletion Problem, where we have an arbitrary number of forbidden connected graphs. For the latter result we present an algorithm that computes the advice complexity directly from F . We give a separate analysis for the Delayed Connected H -Edge-Deletion Problem, which is less general but admits a bound that is easier to compute. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF