Top

Published in:

2020 | OriginalPaper | Chapter

Further Results on Online Node- and Edge-Deletion Problems with Advice

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

Published in: Combinatorial Algorithms

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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 graph classes that can be characterized by forbidden sets of induced subgraphs and analyze the advice complexity of getting an optimal solution. We give almost tight lower and upper bounds for the

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-48966-3_11/MediaObjects/495970_1_En_11_Figa_HTML.gif

, where there is one forbidden induced subgraph that may or may not be disconnected and tight bounds on the

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-48966-3_11/MediaObjects/495970_1_En_11_Figb_HTML.gif

, 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 \(\mathcal{F}\). For the

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-48966-3_11/MediaObjects/495970_1_En_11_Figc_HTML.gif

the advice complexity is basically an easy function of the size of the biggest component in H.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Optimal In-place Algorithms for Basic Graph Problems

next chapter Fair Packing of Independent Sets

Böckenhauer, H., Komm, D., Královic, R., Královic, R., Mömke, T.: On the advice complexity of online problems. In: Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, 16–18 December 2009, Proceedings, pp. 331–340 (2009). https://doi.org/10.1007/978-3-642-10631-6_35

Böckenhauer, H., Komm, D., Královic, R., Královic, R., Mömke, T.: Online algorithms with advice: the tape model. Inf. Comput. 254, 59–83 (2017). https://doi.org/10.1016/j.ic.2017.03.001MathSciNetCrossRefMATH

Böckenhauer, H., Komm, D., Královic, R., Rossmanith, P.: The online knapsack problem: advice and randomization. Theoret. Comput. Sci. 527, 61–72 (2014). https://doi.org/10.1016/j.tcs.2014.01.027MathSciNetCrossRefMATH

Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)MATH

Demange, M., Paschos, V.T.: On-line vertex-covering. Theoret. Comput. Sci. 332(1–3), 83–108 (2005). https://doi.org/10.1016/j.tcs.2004.08.015MathSciNetCrossRefMATH

Descartes, R.: Discours de la methode pour bien conduire sa raison, et chercher la verité dans les sciences. Plus la Dioptriqve. Les Meteores. Et la Geometrie. - Qui sont des essais de cete Methode. De l’Imprimerie de Ian Maire (1637)

Dobrev, S., Královic, R., Pardubská, D.: Measuring the problem-relevant information in input. ITA 43(3), 585–613 (2009). https://doi.org/10.1051/ita/2009012MathSciNetCrossRefMATH

Emek, Y., Fraigniaud, P., Korman, A., Rosén, A.: Online computation with advice. Theoret. Comput. Sci. 412(24), 2642–2656 (2011). https://doi.org/10.1016/j.tcs.2010.08.007MathSciNetCrossRefMATH

Greene, D.H., Knuth, D.E.: Mathematics for the Analysis of Algorithms, 3rd edn. Birkhäuser, Boston (1990)CrossRef

10.

Henrici, P.: Applied and Computational Complex Analysis, vol. 1. Wiley, New York (1988)MATH

11.

Hromkovič, J., Královič, R., Královič, R.: Information complexity of online problems. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 24–36. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15155-2_3CrossRefMATH

12.

Komm, D.: An Introduction to Online Computation - Determinism, Randomization. Advice Texts in Theoretical Computer Science. An EATCS Series. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-42749-2CrossRef

13.

Komm, D., Královic, R., Královic, R., Kudahl, C.: Advice complexity of the online induced subgraph problem. In: Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.) 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, 22–26 August 2016 - Kraków, Poland, LIPIcs, vol. 58, pp. 59:1–59:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016). https://doi.org/10.4230/LIPIcs.MFCS.2016.59

14.

Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. In: Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, 10–15 July 2018, pp. 3302–3311 (2018)

15.

Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In: Advances in Neural Information Processing Systems, vol. 31, pp. 9684–9693 (2018)

16.

Rossmanith, P.: On the advice complexity of online edge- and node-deletion problems. In: Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday, pp. 449–462 (2018). https://doi.org/10.1007/978-3-319-98355-4_26

17.

Yannakakis, M.: Node- and edge-deletion np-complete problems. In: Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., Aho, A.V. (eds.) Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1–3 May 1978, San Diego, California, USA, pp. 253–264. ACM (1978). https://doi.org/10.1145/800133.804355

Title: Further Results on Online Node- and Edge-Deletion Problems with Advice
Authors: Li-Hsuan Chen
Ling-Ju Hung
Henri Lotze
Peter Rossmanith
Publisher: Springer International Publishing
Book: Combinatorial Algorithms
Print ISBN: 978-3-030-48965-6

Electronic ISBN: 978-3-030-48966-3

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-48966-3_11

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner