166 Search Results for "Hoffmann, Jan"

Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-05-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of May 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of May 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-05-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of May 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-05-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-05-01},
    month     = {May},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-05-01
dblp computer science bibliography – Monthly Snapshot XML Release of May 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of May 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-05-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of May 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-05-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-05-01},
    month     = {May},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-04-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of April 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of April 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-04-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of April 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-04-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-04-01},
    month     = {April},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-04-01
dblp computer science bibliography – Monthly Snapshot XML Release of April 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of April 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-04-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of April 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-04-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-04-01},
    month     = {April},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-03-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of March 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of March 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-03-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of March 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-03-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-03-01},
    month     = {March},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-03-01
dblp computer science bibliography – Monthly Snapshot XML Release of March 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of March 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-03-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of March 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-03-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-03-01},
    month     = {March},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-02-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of February 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of February 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-02-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of February 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-02-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-02-01},
    month     = {February},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-02-01
dblp computer science bibliography – Monthly Snapshot XML Release of February 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of February 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-02-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of February 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-02-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-02-01},
    month     = {February},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-01-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of January 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of January 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-01-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of January 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-01-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-01-01},
    month     = {January},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-01-01
dblp computer science bibliography – Monthly Snapshot XML Release of January 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of January 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-01-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of January 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-01-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-01-01},
    month     = {January},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
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}
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2025-12-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of December 2025

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of December 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2025-12-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of December 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2025-12-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2025-12-01},
    month     = {December},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2025-12-01
dblp computer science bibliography – Monthly Snapshot XML Release of December 2025

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of December 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2025-12-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of December 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2025-12-01},
    url       = {https://doi.org/10.4230/dblp.xml.2025-12-01},
    month     = {December},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.23
Precoloring Extension with Demands on Paths

Authors: Arun Kumar Das, Michal Opler, and Tomáš Valla

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

Abstract
Let G be a graph with a set of precolored vertices, and let us be given an integer distance parameter d and a set of integer demands d₁,… ,d_c. The Distance Precoloring Extension with Demands (DPED) problem is to compute a vertex c-coloring of G such that the following three conditions hold: (i) the resulting coloring respects the colors of the precolored vertices, (ii) the distance of two vertices of the same color is at least d, and (iii) the number of vertices colored by color i is exactly d_i. This problem is motivated by a program scheduling in commercial broadcast channels with constraints on content repetition and placement, which leads precisely to the DPED problem for paths. In this paper, we study DPED on paths and present a polynomial time exact algorithm when precolored vertices are restricted to the two ends of the path and devise an approximation algorithm for DPED with an additive approximation factor polynomially bounded by d and the number of precolored vertices. Then, we prove that the Distance Precoloring Extension problem on paths, a less restrictive version of DPED without the demand constraints, and then DPED itself, is NP-complete. Motivated by this result, we further study the parameterized complexity of DPED on paths. We establish that the DPED problem on paths is W[1]-hard when parameterized by the number of colors and the distance. On the positive side, we devise a fixed parameter tractable (FPT) algorithm for DPED on paths when the number of colors, the distance, and the number of precolored vertices are considered as the parameters. Moreover, we prove that Distance Precoloring Extension is FPT parameterized by the distance. As a byproduct, we also obtain several results for the Distance List Coloring problem on paths.
Cite as

Arun Kumar Das, Michal Opler, and Tomáš Valla. Precoloring Extension with Demands on Paths. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2025.23,
  author =	{Das, Arun Kumar and Opler, Michal and Valla, Tom\'{a}\v{s}},
  title =	{{Precoloring Extension with Demands on Paths}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{23:1--23:15},
  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.23},
  URN =		{urn:nbn:de:0030-drops-249319},
  doi =		{10.4230/LIPIcs.ISAAC.2025.23},
  annote =	{Keywords: precoloring extension, distance coloring, FPT, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.16
Structural Parameterizations of k-Planarity

Authors: Tatsuya Gima, Yasuaki Kobayashi, and Yuto Okada

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
The concept of k-planarity is extensively studied in the context of Beyond Planarity. A graph is k-planar if it admits a drawing in the plane in which each edge is crossed at most k times. The local crossing number of a graph is the minimum integer k such that it is k-planar. The problem of determining whether an input graph is 1-planar is known to be NP-complete even for near-planar graphs [Cabello and Mohar, SIAM J. Comput. 2013], that is, the graphs obtained from planar graphs by adding a single edge. Moreover, the local crossing number is hard to approximate within a factor 2 - ε for any ε > 0 [Urschel and Wellens, IPL 2021]. To address this computational intractability, Bannister, Cabello, and Eppstein [JGAA 2018] investigated the parameterized complexity of the case of k = 1, particularly focusing on structural parameterizations on input graphs, such as treedepth, vertex cover number, and feedback edge number. In this paper, we extend their approach by considering the general case k ≥ 1 and give (tight) parameterized upper and lower bound results. In particular, we strengthen the aforementioned lower bound results to subclasses of constant-treewidth graphs: we show that testing 1-planarity is NP-complete even for near-planar graphs with feedback vertex set number at most 3 and pathwidth at most 4, and the local crossing number is hard to approximate within any constant factor for graphs with feedback vertex set number at most 2.
Cite as

Tatsuya Gima, Yasuaki Kobayashi, and Yuto Okada. Structural Parameterizations of k-Planarity. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gima_et_al:LIPIcs.GD.2025.16,
  author =	{Gima, Tatsuya and Kobayashi, Yasuaki and Okada, Yuto},
  title =	{{Structural Parameterizations of k-Planarity}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.16},
  URN =		{urn:nbn:de:0030-drops-250021},
  doi =		{10.4230/LIPIcs.GD.2025.16},
  annote =	{Keywords: 1-planar graphs, local crossing number, beyond planarity, parameterized complexity, kernelization}
}
  • Refine by Type
  • 144 Artifact
  • 22 Document/PDF
  • 19 Document/HTML

  • Refine by Publication Year
  • 10 2026
  • 43 2025
  • 24 2024
  • 25 2023
  • 24 2022
  • Show More...

  • Refine by Author
  • 144 dblp Team
  • 2 Eppstein, David
  • 2 Goodrich, Michael T.
  • 2 Hoffmann, Jan
  • 2 Leopoldseder, David
  • Show More...

  • Refine by Series/Journal
  • 21 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Human-centered computing → Graph drawings
  • 2 Mathematics of computing → Combinatorial optimization
  • 2 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 144 bibliography
  • 144 computer science
  • 144 dblp
  • 144 knowledge graph
  • 144 open data
  • 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