Search Results

Documents authored by van Bevern, René

Document
DOI: 10.4230/OASIcs.ATMOS.2018.10
Parameterized Algorithms and Data Reduction for Safe Convoy Routing

Authors: René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
We study a problem that models safely routing a convoy through a transportation network, where any vertex adjacent to the travel path of the convoy requires additional precaution: Given a graph G=(V,E), two vertices s,t in V, and two integers k,l, we search for a simple s-t-path with at most k vertices and at most l neighbors. We study the problem in two types of transportation networks: graphs with small crossing number, as formed by road networks, and tree-like graphs, as formed by waterways. For graphs with constant crossing number, we provide a subexponential 2^O(sqrt n)-time algorithm and prove a matching lower bound. We also show a polynomial-time data reduction algorithm that reduces any problem instance to an equivalent instance (a so-called problem kernel) of size polynomial in the vertex cover number of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess. Regarding tree-like graphs, we obtain a 2^O(tw) * l^2 * n-time algorithm for graphs of treewidth tw, show that there is no problem kernel with size polynomial in tw, yet show a problem kernel with size polynomial in the feedback edge number of the input graph.
Cite as

René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. Parameterized Algorithms and Data Reduction for Safe Convoy Routing. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:OASIcs.ATMOS.2018.10,
  author =	{van Bevern, Ren\'{e} and Fluschnik, Till and Tsidulko, Oxana Yu.},
  title =	{{Parameterized Algorithms and Data Reduction for Safe Convoy Routing}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{10:1--10:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.10},
  URN =		{urn:nbn:de:0030-drops-97157},
  doi =		{10.4230/OASIcs.ATMOS.2018.10},
  annote =	{Keywords: NP-hard problem, fixed-parameter tractability, problem kernelization, shortest path, secluded solution}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.5
Finding Secluded Places of Special Interest in Graphs

Authors: René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.
Cite as

René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Finding Secluded Places of Special Interest in Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:LIPIcs.IPEC.2016.5,
  author =	{van Bevern, Ren\'{e} and Fluschnik, Till and Mertzios, George B. and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej},
  title =	{{Finding Secluded Places of Special Interest in Graphs}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.5},
  URN =		{urn:nbn:de:0030-drops-69380},
  doi =		{10.4230/LIPIcs.IPEC.2016.5},
  annote =	{Keywords: Neighborhood, Feedback Vertex Set, Vertex Deletion, Separator, Dominating Set}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2015.130
Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems

Authors: René van Bevern, Christian Komusiewicz, and Manuel Sorge

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract
We show that any alpha(n)-approximation algorithm for the n-vertex metric asymmetric Traveling Salesperson problem yields O(alpha(C))-approximation algorithms for various mixed, windy, and capacitated arc routing problems. Herein, C is the number of weakly-connected components in the subgraph induced by the positive-demand arcs, a number that can be expected to be small in applications. In conjunction with known results, we derive constant-factor approximations if C is in O(log n) and O(log(C)/log(log(C)))-approximations in general.
Cite as

René van Bevern, Christian Komusiewicz, and Manuel Sorge. Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 130-143, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:OASIcs.ATMOS.2015.130,
  author =	{van Bevern, Ren\'{e} and Komusiewicz, Christian and Sorge, Manuel},
  title =	{{Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{130--143},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.130},
  URN =		{urn:nbn:de:0030-drops-54575},
  doi =		{10.4230/OASIcs.ATMOS.2015.130},
  annote =	{Keywords: vehicle routing, transportation, Rural Postman, Chinese Postman, NP- hard problem, parameterized algorithm, combinatorial optimization}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact