Zobrazeno 1 - 10
of 25
pro vyhledávání: '"Tsidulko, Oxana Yu."'
Autor:
van Bevern, René, Kirilin, Artem M., Skachkov, Daniel A., Smirnov, Pavel V., Tsidulko, Oxana Yu.
Publikováno v:
Journal of Computer and System Sciences 139:103479, 2024
The NP-hard Multiple Hitting Set problem is finding a minimum-cardinality set intersecting each of the sets in a given input collection a given number of times. Generalizing a well-known data reduction algorithm due to Weihe, we show a problem kernel
Externí odkaz:
http://arxiv.org/abs/2109.06042
Autor:
van Bevern, René, Kirilin, Artem M., Skachkov, Daniel A., Smirnov, Pavel V., Tsidulko, Oxana Yu.
Publikováno v:
In Journal of Computer and System Sciences February 2024 139
Publikováno v:
Operations Research Letters, 49(2): 270-277, 2021
The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on o
Externí odkaz:
http://arxiv.org/abs/2011.04022
Publikováno v:
Networks 76(4):485-508, 2020
Given an undirected graph with edge weights and a subset $R$ of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of $R$. We prove that RPP is WK[1]-complete parameterized by the number a
Externí odkaz:
http://arxiv.org/abs/1812.10131
Publikováno v:
Discrete Applied Mathematics, 298: 110-128, 2021
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:
http://arxiv.org/abs/1806.11527
Publikováno v:
Networks, 75(1):34-63, 2020
Given a graph $G=(V,E)$, two vertices $s,t\in V$, and two integers $k,\ell$, the Short Secluded Path problem is to find a simple $s$-$t$-path with at most $k$ vertices and $\ell$ neighbors. We study the parameterized complexity of the problem with re
Externí odkaz:
http://arxiv.org/abs/1806.09540
Publikováno v:
In Discrete Applied Mathematics 31 July 2021 298:110-128
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
In Operations Research Letters March 2021 49(2):270-277
Presentation for the article of the same name, to appear in Discrete Applied Mathematics
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::be9249c6e571d510fb7c6d3fee1737ea