Zobrazeno 1 - 10
of 86
pro vyhledávání: '"Hans-Joachim Böckenhauer"'
Publikováno v:
Theoretical Computer Science. 918:77-93
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9e3da73f6905de65b64efb9435e9fc20
https://doi.org/10.1016/j.tcs.2022.03.022
https://doi.org/10.1016/j.tcs.2022.03.022
Publikováno v:
Structural Information and Communication Complexity ISBN: 9783031327322
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e63705e9c1ce45be31ad4b7c2aac6570
https://doi.org/10.1007/978-3-031-32733-9_11
https://doi.org/10.1007/978-3-031-32733-9_11
Publikováno v:
Information and Computation, 289 (Part A)
Graph exploration is a theoretical model of the crucial task of moving an agent through an unknown environment. Here, an algorithm has to guide an explorer through a network with n vertices and m edges, visiting every vertex at least once. We conside
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9d32de933a41a48291f317920ac7c227
https://hdl.handle.net/20.500.11850/599612
https://hdl.handle.net/20.500.11850/599612
Publikováno v:
Communications in Computer and Information Science ISBN: 9789811995811
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::796089acc5a054d468148ea80acee077
https://doi.org/10.1007/978-981-19-9582-8_3
https://doi.org/10.1007/978-981-19-9582-8_3
Publikováno v:
Acta informatica, 59 (4)
Acta informatica 59(4), 427-450 (2022). doi:10.1007/s00236-022-00428-y special issue: "Special Issue: Klaus-Jörn Lange Festschrift / Issue editors: Henning Fernau, Markus Holzer, Petra Wolf"
Acta informatica 59(4), 427-450 (2022). doi:10.1007/s00236-022-00428-y special issue: "Special Issue: Klaus-Jörn Lange Festschrift / Issue editors: Henning Fernau, Markus Holzer, Petra Wolf"
Parameterized complexity allows us to analyze the time complexity of problems with respect to a natural parameter depending on the problem. Reoptimization looks for solutions or approximations for problem instances when given solutions to neighboring
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f391ef8c78cfb7c543ec957b72564ea6
https://pubmed.ncbi.nlm.nih.gov/36045930
https://pubmed.ncbi.nlm.nih.gov/36045930
Publikováno v:
Theoretical Computer Science, 862
Theoretical computer science 862, 81-96 (2021). doi:10.1016/j.tcs.2021.01.022 special issue: "A Fascinating Rainbow of Computation – Honoring Gheorghe Păun on the Occasion of His 70th Birthday / Edited by Lila Kari, Grzegorz Rozenberg, Arto Salomaa, Ion Petre"
Theoretical computer science 862, 81-96 (2021). doi:10.1016/j.tcs.2021.01.022 special issue: "A Fascinating Rainbow of Computation – Honoring Gheorghe Păun on the Occasion of His 70th Birthday / Edited by Lila Kari, Grzegorz Rozenberg, Arto Salomaa, Ion Petre"
A dominating set S of a graph is a set of vertices such that each vertex is in S or has a neighbor in S. The goal of the dominating set problem is to find such a set of minimum cardinality. In the online setting, the graph is revealed vertex by verte
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b80a7329a105324e8662af86085cd318
https://hdl.handle.net/20.500.11850/471612
https://hdl.handle.net/20.500.11850/471612
Autor:
Dennis Komm, Beatrice Palano, Tatjana Brülisauer, Maria Paola Bianchi, Hans-Joachim Böckenhauer
Publikováno v:
International Journal of Foundations of Computer Science, 29 (4)
Lecture Notes in Computer Science ISBN: 9783662491911
Lecture Notes in Computer Science ISBN: 9783662491911
In the online minimum spanning tree problem, a graph is revealed vertex by vertex; together with every vertex, all edges to vertices that are already known are given, and an online algorithm must irrevocably choose a subset of them as a part of its s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::52e4d7059d9dc2f53c5b21688c28be1b
https://doi.org/10.1142/s0129054118410034
https://doi.org/10.1142/s0129054118410034
Publikováno v:
Information and Computation. 254:59-83
We investigate to what extent the solution quality of online algorithms can be improved when supplying them with information about the input. To this end, we refine the recently introduced notion of advice complexity where the algorithm has access to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b789ee398508aaa8c1e8b3bdcd42c4b8
https://doi.org/10.1016/j.ic.2017.03.001
https://doi.org/10.1016/j.ic.2017.03.001
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030250041
A well-studied problem in the online setting, where requests have to be answered immediately without knowledge of future requests, is the call admission problem. In this problem, we are given nodes in a communication network that request connections
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8dcfa19afda5bc66355de79d3ff03468
https://doi.org/10.1007/978-3-030-25005-8_10
https://doi.org/10.1007/978-3-030-25005-8_10
Publikováno v:
Handbook of Approximation Algorithms and Metaheuristics, Second Edition ISBN: 9781351236423
Handbook of Approximation Algorithms and Metaheuristics
Chapman & Hall/CRC Computer & Information Science Series ISBN: 9781584885504
Handbook of Approximation Algorithms and Metaheuristics
Chapman & Hall/CRC Computer & Information Science Series ISBN: 9781584885504
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8a40d2a20775195a015e9ff03625056e
https://doi.org/10.1201/9781351236423-27
https://doi.org/10.1201/9781351236423-27