Zobrazeno 1 - 10
of 14
pro vyhledávání: '"Philipp Zschoche"'
Publikováno v:
Algorithmica.
Addressing a quest by Gupta et al. (in: Proceedings of the 41st international colloquium on automata, languages, and programming (ICALP 2014), vol 8572 of LNCS. Springer, pp 563–575, 2014), we provide a first, comprehensive study of finding a short
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::089150b176bf672f558651665843a1d8
https://doi.org/10.1007/s00453-022-01077-w
https://doi.org/10.1007/s00453-022-01077-w
Publikováno v:
30th International Joint Conference on Artificial Intelligence (IJCAI-21), Montreal, Quebec, 21-26 Aug 2021 [Conference proceedings]
IJCAI
IJCAI
We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing tim
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8f4bdf017bdb3377e41ee7c51cbd2fe9
https://doi.org/10.1007/s10458-022-09583-5
https://doi.org/10.1007/s10458-022-09583-5
Publikováno v:
Discrete Applied Mathematics. 298:110-128
We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractabil
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8975a247315ffaa30382652b3ee3c773
https://doi.org/10.1016/j.dam.2021.03.014
https://doi.org/10.1016/j.dam.2021.03.014
We study the network untangling problem introduced by Rozenshtein, Tatti, and Gionis [DMKD 2021], which is a variant of Vertex Cover on temporal graphs -- graphs whose edge set changes over discrete time steps. They introduce two problem variants. Th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5b8f0a12f5ec31dfa3811d88416bbbf5
Autor:
Stefan Schmid, Rolf Niedermeier, Leon Kellerhals, Philipp Zschoche, Matthias Rost, Aleksander Figiel
Publikováno v:
SPAA
The performance of distributed and data-centric applications often critically depends on the interconnecting network. Applications are hence modeled as virtual networks, also accounting for resource demands on links. At the heart of provisioning such
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a4cfcf9cbbd2edbb5255d1f6646b5ebd
http://arxiv.org/abs/2105.07006
http://arxiv.org/abs/2105.07006
Autor:
Philipp Zschoche
A temporal graph is a sequence of graphs (called layers) over the same vertex set—describing a graph topology which is subject to discrete changes over time. A Δ-temporal matching M is a set of time edges ( e , t ) (an edge e paired up with a poin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3ca1ea52109445be860435f6c121eece
http://arxiv.org/abs/2010.10408
http://arxiv.org/abs/2010.10408
Publikováno v:
Treewidth, Kernels, and Algorithms ISBN: 9783030420703
Treewidth, Kernels, and Algorithms
Treewidth, Kernels, and Algorithms
Treewidth is arguably the most important structural graph parameter leading to algorithmically beneficial graph decompositions. Triggered by a strongly growing interest in temporal networks (graphs where edge sets change over time), we discuss fresh
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a1a3cbb7127de57a0ec6765d2570569b
https://doi.org/10.1007/978-3-030-42071-0_6
https://doi.org/10.1007/978-3-030-42071-0_6
Covering all edges of a graph by a small number of vertices, this is the NP-complete Vertex Cover problem. It is among the most fundamental graph-algorithmic problems. Following a recent trend in studying temporal graphs (a sequence of graphs, so-cal
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::75fd11391e6afe7250a75126c25ef384
http://arxiv.org/abs/1906.00659
http://arxiv.org/abs/1906.00659
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030174019
CIAC
CIAC
We consider an uncapacitated discrete facility location problem where the task is to decide which facilities to open and which clients to serve for maximum profit so that the facilities form an independent set in given facility-side matroids and the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3b83ea4e30cdedd200cc09b7094ab007
https://doi.org/10.1007/978-3-030-17402-6_6
https://doi.org/10.1007/978-3-030-17402-6_6
Publikováno v:
Graph-Theoretic Concepts in Computer Science ISBN: 9783030002558
WG
WG
We investigate the computational complexity of separating two distinct vertices s and z by vertex deletion in a temporal graph. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal (
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c7b4285fdc56c3a4c86c6be067144242
https://doi.org/10.1007/978-3-030-00256-5_18
https://doi.org/10.1007/978-3-030-00256-5_18