3 Search Results for "Burkhard, Hans-Dieter"

Document
DOI: 10.4230/LIPIcs.IPEC.2025.30
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers

Authors: Jesse Beisegel, Katharina Klost, Kristin Knorr, Fabienne Ratajczak, and Robert Scheffler

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems Hamiltonian Path and Hamiltonian Cycle are in FPT. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are W[1]-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in XP time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some FPT algorithms, e.g., for edge distance to block. Additionally, we prove para-NP-hardness when considered with the edge clique cover number.
Cite as

Jesse Beisegel, Katharina Klost, Kristin Knorr, Fabienne Ratajczak, and Robert Scheffler. A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.IPEC.2025.30,
  author =	{Beisegel, Jesse and Klost, Katharina and Knorr, Kristin and Ratajczak, Fabienne and Scheffler, Robert},
  title =	{{A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.30},
  URN =		{urn:nbn:de:0030-drops-251623},
  doi =		{10.4230/LIPIcs.IPEC.2025.30},
  annote =	{Keywords: Hamiltonian path, Hamiltonian cycle, partial order, graph width parameter, parameterized complexity}
}
Document
DOI: 10.4230/DagSemProc.06251.1
06251 Abstracts Collection – Multi-Robot Systems: Perception, Behaviors, Learning, and Action

Authors: Hans-Dieter Burkhard, Martin Riedmiller, Uwe Schwiegelshohn, and Manuela Veloso

Published in: Dagstuhl Seminar Proceedings, Volume 6251, Multi-Robot Systems: Perception, Behaviors, Learning, and Action (2006)

Abstract
From 19.06.06 to 23.06.06, the Dagstuhl Seminar 06251 ``Multi-Robot Systems: Perception, Behaviors, Learning, and Action'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Hans-Dieter Burkhard, Martin Riedmiller, Uwe Schwiegelshohn, and Manuela Veloso. 06251 Abstracts Collection – Multi-Robot Systems: Perception, Behaviors, Learning, and Action. In Multi-Robot Systems: Perception, Behaviors, Learning, and Action. Dagstuhl Seminar Proceedings, Volume 6251, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{burkhard_et_al:DagSemProc.06251.1,
  author =	{Burkhard, Hans-Dieter and Riedmiller, Martin and Schwiegelshohn, Uwe and Veloso, Manuela},
  title =	{{06251 Abstracts Collection – Multi-Robot Systems: Perception, Behaviors, Learning, and Action}},
  booktitle =	{Multi-Robot Systems: Perception, Behaviors, Learning, and Action},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6251},
  editor =	{Hans-Dieter Burkhard and Martin Riedmiller and Uwe Schwiegelshohn and Manuela Veloso},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06251.1},
  URN =		{urn:nbn:de:0030-drops-8444},
  doi =		{10.4230/DagSemProc.06251.1},
  annote =	{Keywords: Autonomous robots, multi-robot systems, object recognition, robot-human interaction, modeling, robot simulation}
}
Document
DOI: 10.4230/DagSemProc.06251.2
06251 Executive Summary – Multi-Robot Systems: Perception, Behaviors, Learning, and Action

Authors: Uwe Schwiegelshohn, Walter Nistico, and Matthias Hebbel

Published in: Dagstuhl Seminar Proceedings, Volume 6251, Multi-Robot Systems: Perception, Behaviors, Learning, and Action (2006)

Abstract
The Dagstuhl Seminar on Multi-Robot Systems (06251) was held in June 20-23, 2006. It had the goal to bring researchers together from different areas of robotics to discuss current research topics on autonomous and interacting robots. The technical focus was on perception, behaviors, learning, and action. The seminar took directly place after the RoboCup robot soccer competitions and the subsequent symposium in Bremen. Thus researchers from many different countries were able to join the seminar and address issues without taking into account upcoming competitions or events.
Cite as

Uwe Schwiegelshohn, Walter Nistico, and Matthias Hebbel. 06251 Executive Summary – Multi-Robot Systems: Perception, Behaviors, Learning, and Action. In Multi-Robot Systems: Perception, Behaviors, Learning, and Action. Dagstuhl Seminar Proceedings, Volume 6251, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schwiegelshohn_et_al:DagSemProc.06251.2,
  author =	{Schwiegelshohn, Uwe and Nistico, Walter and Hebbel, Matthias},
  title =	{{06251 Executive Summary – Multi-Robot Systems: Perception, Behaviors, Learning, and Action}},
  booktitle =	{Multi-Robot Systems: Perception, Behaviors, Learning, and Action},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6251},
  editor =	{Hans-Dieter Burkhard and Martin Riedmiller and Uwe Schwiegelshohn and Manuela Veloso},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06251.2},
  URN =		{urn:nbn:de:0030-drops-8432},
  doi =		{10.4230/DagSemProc.06251.2},
  annote =	{Keywords: Summary}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 2 2006

  • Refine by Author
  • 2 Schwiegelshohn, Uwe
  • 1 Beisegel, Jesse
  • 1 Burkhard, Hans-Dieter
  • 1 Hebbel, Matthias
  • 1 Klost, Katharina
  • Show More...

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

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Autonomous robots
  • 1 Hamiltonian cycle
  • 1 Hamiltonian path
  • 1 Summary
  • 1 graph width parameter
  • 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