2 Search Results for "Casetti, Claudio"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.15
Parameterized Complexity of Directed Traveling Salesman Problem

Authors: Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be visited multiple times. The goal is to find a directed closed walk of minimum length (or total weight) that visits every vertex of the given graph at least once. In a yet more general version, Directed Waypoint Routing Problem (DWRP), some vertices are marked as terminals and we are only required to visit all terminals. Furthermore, each edge has its capacity bounding the number of times this edge can be used by a solution. While both problems (and many other variants of TSP) were extensively investigated, mostly from the approximation point of view, there are surprisingly few results concerning the parameterized complexity. Our starting point is the result of Marx et al. [APPROX/RANDOM 2016] who proved that DTSP is W[1]-hard parameterized by distance to pathwidth 3. In this paper we aim to initiate the systematic complexity study of variants of Directed Traveling Salesman Problem with respect to various, mostly structural, parameters. We show that DWRP is FPT parameterized by the solution size, the feedback edge number and the vertex integrity of the underlying undirected graph. Furthermore, the problem is XP parameterized by treewidth. On the complexity side, we show that the problem is W[1]-hard parameterized by the distance to constant treedepth.
Cite as

Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý. Parameterized Complexity of Directed Traveling Salesman Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ISAAC.2025.15,
  author =	{Bla\v{z}ej, V\'{a}clav and Feldmann, Andreas Emil and Fioravantes, Foivos and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej},
  title =	{{Parameterized Complexity of Directed Traveling Salesman Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.15},
  URN =		{urn:nbn:de:0030-drops-249231},
  doi =		{10.4230/LIPIcs.ISAAC.2025.15},
  annote =	{Keywords: Directed TSP, parameterized complexity, vertex integrity, treedepth}
}
Document
DOI: 10.4230/DagSemProc.10402.2
10402 Report – Working Group on Communication Patterns

Authors: Claudio Casetti, Falko Dressler, Lars Eggert, Felix Schmidt-Eisenlohr, Jerome Haerri, Ozan K. Tonguz, Jörg Ott, and Lars Wischhof

Published in: Dagstuhl Seminar Proceedings, Volume 10402, Inter-Vehicular Communication (2011)

Abstract
The objective of the working group communication patterns during the Dagstuhl Seminar on Vehicular Networks has been to review the current status of the communication patterns and principles and discuss the upcoming challenges the community will face in the near future. This is an executive summary of the discussions during the sessions.
Cite as

Claudio Casetti, Falko Dressler, Lars Eggert, Felix Schmidt-Eisenlohr, Jerome Haerri, Ozan K. Tonguz, Jörg Ott, and Lars Wischhof. 10402 Report – Working Group on Communication Patterns. In Inter-Vehicular Communication. Dagstuhl Seminar Proceedings, Volume 10402, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{casetti_et_al:DagSemProc.10402.2,
  author =	{Casetti, Claudio and Dressler, Falko and Eggert, Lars and Schmidt-Eisenlohr, Felix and Haerri, Jerome and Tonguz, Ozan K. and Ott, J\"{o}rg and Wischhof, Lars},
  title =	{{10402 Report – Working Group on Communication Patterns}},
  booktitle =	{Inter-Vehicular Communication},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10402},
  editor =	{Falko Dressler and Frank Kargl and J\"{o}rg Ott and Ozan K. Tonguz and Lars Wischhof},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10402.2},
  URN =		{urn:nbn:de:0030-drops-29287},
  doi =		{10.4230/DagSemProc.10402.2},
  annote =	{Keywords: V2V, communication principles}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2011

  • Refine by Author
  • 1 Blažej, Václav
  • 1 Casetti, Claudio
  • 1 Dressler, Falko
  • 1 Eggert, Lars
  • 1 Feldmann, Andreas Emil
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Directed TSP
  • 1 V2V
  • 1 communication principles
  • 1 parameterized complexity
  • 1 treedepth
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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