17 Search Results for "Katoh, Naoki"

Document
DOI: 10.4230/LIPIcs.SEA.2026.8
General Multiplicative Spanners in Practice

Authors: Fritz Bökler, Markus Chimani, and Henning Jasper

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Given an undirected graph G with edge weights and lengths, a minimum α-spanner is a least-weight subgraph H ⊆ G that preserves distances w.r.t. the lengths between all node pairs up to a factor of α. Literature often takes the simplifying assumption of a single (coupled) edge function for weights and lengths. For such instances, several exact and non-exact algorithms are known and have been thoroughly evaluated in practice. However, many practical instances have decoupled form, as their weights and lengths are generally independent. Due to the increased complexity, only few (and even fewer practical) algorithms are able to guarantee low-weight solutions. This prompts practitioners to force their naturally decoupled instances into a coupled format, forsaking any quality guarantee. We implement several exact, approximative and heuristic algorithms for decoupled α-spanners, and use algorithm engineering to speed them up in practice. Our hypothesis-driven experiments evaluate their performance w.r.t. solution quality and speed. Generally, many practical instances can indeed be solved exactly within reasonable time, while LP-based approximation algorithms are not worthwhile. We find that standard greedy algorithms often yield acceptable results, but there are also practical instances for which they yield arbitrarily poor solutions. Here, augmented greedy variations offer a good compromise between solution quality and speed.
Cite as

Fritz Bökler, Markus Chimani, and Henning Jasper. General Multiplicative Spanners in Practice. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bokler_et_al:LIPIcs.SEA.2026.8,
  author =	{B\"{o}kler, Fritz and Chimani, Markus and Jasper, Henning},
  title =	{{General Multiplicative Spanners in Practice}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{8:1--8:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.8},
  URN =		{urn:nbn:de:0030-drops-260120},
  doi =		{10.4230/LIPIcs.SEA.2026.8},
  annote =	{Keywords: Graph spanners, ILP, experimental study, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.33
Near-Optimal Bounds for Parameterized Euclidean k-Means

Authors: Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The k-means problem is a classic objective for modeling clustering in a metric space. Given a set of points in a metric space, the goal is to find k representative points so as to minimize the sum of the squared distances from each point to its closest representative. In this work, we study the approximability of k-means in Euclidean spaces parameterized by the number of clusters, k. In seminal works, de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] showed how to obtain a (1+ε)-approximation for high-dimensional Euclidean k-means in time 2^{(k/ε)^O(1)} ⋅ dn^O(1). In this work, we introduce a new fine-grained hypothesis called Exponential Time for Expanders Hypothesis (XXH) which roughly asserts that there are no non-trivial exponential time approximation algorithms for the vertex cover problem on near perfect vertex expanders. Assuming XXH, we close the above long line of work on approximating Euclidean k-means by showing that there is no 2^{(k/ε)^{1-o(1)}} ⋅ n^O(1) time algorithm achieving a (1+ε)-approximation for k-means in Euclidean space. This lower bound is tight as it matches the algorithm given by Feldman, Monemizadeh, and Sohler [SoCG'07] whose runtime is 2^O(k/ε) + O(ndk). Furthermore, assuming XXH, we show that the seminal O(n^{kd+1}) runtime exact algorithm of Inaba, Katoh, and Imai [SoCG'94] for k-means is optimal for small values of k.
Cite as

Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn. Near-Optimal Bounds for Parameterized Euclidean k-Means. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohenaddad_et_al:LIPIcs.SoCG.2026.33,
  author =	{Cohen-Addad, Vincent and C. S., Karthik and Saulpic, David and Schwiegelshohn, Chris},
  title =	{{Near-Optimal Bounds for Parameterized Euclidean k-Means}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.33},
  URN =		{urn:nbn:de:0030-drops-258391},
  doi =		{10.4230/LIPIcs.SoCG.2026.33},
  annote =	{Keywords: k-means clustering, Euclidean space, Fine-Grained Complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.34
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces

Authors: Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The k-median and k-means clustering objectives are classic objectives for modeling clustering in a metric space. Given a set of points in a metric space, the goal of the k-median (resp. k-means) problem is to find k representative points so as to minimize the sum of the distances (resp. sum of squared distances) from each point to its closest representative. Cohen-Addad, Feldmann, and Saulpic [JACM'21] showed how to obtain a (1+ε)-factor approximation in low-dimensional Euclidean metric for both the k-median and k-means problems in near-linear time 2^{(1/ε)^O(d²)} n ⋅ polylog(n) (where d is the dimension and n is the number of input points). We improve this running time to 2^{O(1/ε)^{d-1}} ⋅ n ⋅ polylog(n), and show an almost matching lower bound: under the Gap Exponential Time Hypothesis for 3-SAT, there is no 2^o(1/ε^{d-1}) n^O(1) algorithm achieving a (1+ε)-approximation for k-means.
Cite as

Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn. Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohenaddad_et_al:LIPIcs.SoCG.2026.34,
  author =	{Cohen-Addad, Vincent and Karthik C. S. and Saulpic, David and Schwiegelshohn, Chris},
  title =	{{Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.34},
  URN =		{urn:nbn:de:0030-drops-258404},
  doi =		{10.4230/LIPIcs.SoCG.2026.34},
  annote =	{Keywords: k-means clustering, k-median clustering, Euclidean space, Fine-Grained Complexity}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2026.98
Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams (Media Exposition)

Authors: Carlos Alegría, Ioannis Mantas, Marko Savić, and Martin Suderland

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Floodlight illumination problems are art-gallery variants, where a target domain needs to be illuminated by guards, each associated with a field of view. The rotating rays Voronoi diagram is a Voronoi diagram with rays as sites under the angular distance. There is a natural connection of this Voronoi structure with the problem of finding the minimum aperture such that a given set of uniform aperture floodlights illuminates a target domain. In this work we present an interactive visualization software for such problems, supporting different angular distances, namely, oriented and unoriented versions, and for different domains, namely, the plane and simple polygons.
Cite as

Carlos Alegría, Ioannis Mantas, Marko Savić, and Martin Suderland. Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 98:1-98:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alegria_et_al:LIPIcs.SoCG.2026.98,
  author =	{Alegr{\'\i}a, Carlos and Mantas, Ioannis and Savi\'{c}, Marko and Suderland, Martin},
  title =	{{Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{98:1--98:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.98},
  URN =		{urn:nbn:de:0030-drops-259048},
  doi =		{10.4230/LIPIcs.SoCG.2026.98},
  annote =	{Keywords: rotating rays Voronoi diagram, oriented angular distance, unoriented angular distance, Brocard angle, floodlight illumination, coverage problems, visualization software}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2026.10
Bounding the Makespan of Transaction Schedules

Authors: Tim Baccaert, Brecht Vandevoort, and Bas Ketsman

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
The performance of transactional database systems is typically evaluated by measuring the amount of transactions they can commit to the database per second. However, fairly measuring this for the same workload on different systems is not trivial. It is therefore relevant to formalize schedule efficiency, investigate the space of all possible efficient schedules, and identify whether there is any room for improvement. Prior transaction theory largely centers on decision problems relating to safety, such as the serializability, robustness, and allocation problems. Most pertinently, these problems take already scheduled transactions as input, and do not directly consider the efficiency of those schedules. In this work, we define schedules as assignments of operations on objects to discrete points in time. This allows us to quantify efficiency as the elapsed duration between the schedule’s beginning and end, more commonly known as the makespan in the scheduling literature. We establish that, given some set of transactions and a desired makespan, it is NP-complete to decide if there exists a conflict serializable schedule which is bounded by that makespan. We additionally provide an instance optimal algorithm for scheduling transaction sets with a single contention point, that is, exactly one object may appear in conflicting operations. Lastly, we give worst-case optimal bounds on the makespan, meaning that schedules can never exceed this bound, and for the worst transaction sets, the bound is optimal.
Cite as

Tim Baccaert, Brecht Vandevoort, and Bas Ketsman. Bounding the Makespan of Transaction Schedules. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baccaert_et_al:LIPIcs.ICDT.2026.10,
  author =	{Baccaert, Tim and Vandevoort, Brecht and Ketsman, Bas},
  title =	{{Bounding the Makespan of Transaction Schedules}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.10},
  URN =		{urn:nbn:de:0030-drops-256242},
  doi =		{10.4230/LIPIcs.ICDT.2026.10},
  annote =	{Keywords: Transactions, Scheduling, Discrete Optimization, Complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.13
Line Cover and Related Problems

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study several extensions of the classic Line Cover problem of covering a set of n points in the plane with k lines. Line Cover is known to be NP-hard and our focus is on two natural generalizations: (1) Line Clustering, where the objective is to find k lines in the plane that minimize the sum of squares of distances of a given set of input points to the closest line, and (2) Hyperplane Cover, where the goal is to cover n points in ℝ^d by k hyperplanes. We also consider the more general Projective Clustering problem, which unifies both of these and has numerous applications in machine learning, data mining, and computational geometry. In this problem one seeks k affine subspaces of dimension r minimizing the sum of squares of distances of a given set of n points in ℝ^d to the closest point within one of the k affine subspaces. Our main contributions reveal interesting differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable parameterized by the number k of lines in the solution, we show that Line Clustering is W[1]-hard when parameterized by k and rule out algorithms of running time n^{o(k)} under the Exponential Time Hypothesis. Hyperplane Cover is known to be NP-hard even when d = 2 and by the work of Langerman and Morin [Discrete & Computational Geometry, 2005], it is FPT parameterized by k and d. We complement this result by establishing that Hyperplane Cover is W[2]-hard when parameterized by only k. We complement our hardness results by presenting an algorithm for Projective Clustering. We show that this problem is solvable in n^{𝒪(dk(r+1))} time. Not only does this yield an upper bound for Line Clustering that asymptotically matches our lower bound, but it also significantly extends the seminal work on k-Means Clustering (the special case r = 0) by Inaba, Katoh, and Imai [SoCG 1994].
Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana. Line Cover and Related Problems. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.13,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Saha, Souvik and Seetharaman, Sanjay and Upasana, Anannya},
  title =	{{Line Cover and Related Problems}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.13},
  URN =		{urn:nbn:de:0030-drops-255023},
  doi =		{10.4230/LIPIcs.STACS.2026.13},
  annote =	{Keywords: Point Line Cover, Projective Clustering, W-hardness, XP algorithm}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.14
OOPS: Optimized One-Planarity Solver via SAT

Authors: Sergey Pupyrev

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

Abstract
We present OOPS (Optimized One-Planarity Solver), a practical heuristic for recognizing 1-planar graphs and several important subclasses. A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once - a natural generalization of planar graphs that has received increasing attention in graph drawing and beyond-planar graph theory. Although testing planarity can be done in linear time, recognizing 1-planar graphs is NP-complete, making effective practical algorithms especially valuable. The core idea of our approach is to reduce the recognition of 1-planarity to a propositional satisfiability (SAT) instance, enabling the use of modern SAT solvers to efficiently explore the search space. Despite the inherent complexity of the problem, our method is substantially faster in practice than naïve or brute-force algorithms. In addition to demonstrating the empirical performance of our solver on synthetic and real-world instances, we show how OOPS can be used as a discovery tool in theoretical graph theory. Specifically, we employ OOPS to investigate two research problems concerning 1-planarity of specific graph families. Our implementation of the algorithm is publicly available to support further exploration in the field.
Cite as

Sergey Pupyrev. OOPS: Optimized One-Planarity Solver via SAT. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pupyrev:LIPIcs.GD.2025.14,
  author =	{Pupyrev, Sergey},
  title =	{{OOPS: Optimized One-Planarity Solver via SAT}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{14:1--14:19},
  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.14},
  URN =		{urn:nbn:de:0030-drops-250004},
  doi =		{10.4230/LIPIcs.GD.2025.14},
  annote =	{Keywords: beyond planarity, 1-planar graph, SAT, book embeddings, upward 1-planarity}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.4
Heuristics for Exact 1-Planarity Testing

Authors: Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter

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

Abstract
Since many real-world graphs are nonplanar, the study of graphs that allow few crossings per edge has been an active subfield of graph theory in recent years. One of the most natural generalizations of planar graphs are the so-called 1-planar graphs that admit a drawing with at most one crossing per edge. Unfortunately, testing whether a graph is 1-planar is known to be NP-complete even for very restricted graph classes. On the positive side, Binucci, Didimo and Montecchiani [Binucci et al., 2023] presented the first practical algorithm for testing 1-planarity based on an easy-to-implement backtracking strategy. We build on this idea and systematically explore the design choices of such algorithms and propose several new ingredients, such as different branching strategies and multiple filter criteria that allow us to reject certain branches in the search tree early on. We conduct an extensive experimental evaluation that evaluates the efficiency and effectiveness of these ingredients. Given a time limit of three hours per instance, our best configuration is able to solve more than 95% of the non-planar instances from the well-known North and Rome graphs with up to 50 vertices. Notably, the median running time for solved instances is well below 4 seconds.
Cite as

Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter. Heuristics for Exact 1-Planarity Testing. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fink_et_al:LIPIcs.GD.2025.4,
  author =	{Fink, Simon D. and M\"{u}nch, Miriam and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Heuristics for Exact 1-Planarity Testing}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{4:1--4:19},
  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.4},
  URN =		{urn:nbn:de:0030-drops-249909},
  doi =		{10.4230/LIPIcs.GD.2025.4},
  annote =	{Keywords: 1-Planarity, Experiments, Backtracking}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.23
Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter

Authors: Gianmarco Picarella, Marc van Kreveld, Frank Staals, and Sjoerd de Vries

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We study the problem of computing a convex region with bounded area and diameter that contains the maximum number of points from a given point set P. We show that this problem can be solved in O(n⁶k) time and O(n³k) space, where n is the size of P and k is the maximum number of points in the found region. We experimentally compare this new algorithm with an existing algorithm that does the same but without the diameter constraint, which runs in O(n³k) time. For the new algorithm, we use different diameters. We use both synthetic data and data from an application in cancer detection, which motivated our research.
Cite as

Gianmarco Picarella, Marc van Kreveld, Frank Staals, and Sjoerd de Vries. Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{picarella_et_al:LIPIcs.ESA.2025.23,
  author =	{Picarella, Gianmarco and van Kreveld, Marc and Staals, Frank and de Vries, Sjoerd},
  title =	{{Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.23},
  URN =		{urn:nbn:de:0030-drops-244919},
  doi =		{10.4230/LIPIcs.ESA.2025.23},
  annote =	{Keywords: convex polygon, dynamic programming, implementation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.93
Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity

Authors: Jingyang Zhao and Mingyu Xiao

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
The Capacitated Vehicle Routing Problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. Based on customer demand, we distinguish three variants of CVRP: unit-demand, splittable, and unsplittable. In this paper, we consider k-CVRP in general metrics and on general graphs, where k is the vehicle capacity. All three versions are APX-hard for any fixed k ≥ 3. Assume that the approximation ratio of metric TSP is 3/2. We present a (5/2 - Θ(√{1/k}))-approximation algorithm for the splittable and unit-demand cases, and a (5/2 + ln 2 - Θ(√{1/k}))-approximation algorithm for the unsplittable case. Our approximation ratio is better than the previous results when k is less than a sufficiently large value, approximately 1.7 x 10⁷. For small values of k, we design independent and elegant algorithms with further improvements. For the splittable and unit-demand cases, we improve the approximation ratio from 1.792 to 1.500 for k = 3, and from 1.750 to 1.500 for k = 4. For the unsplittable case, we improve the approximation ratio from 1.792 to 1.500 for k = 3, from 2.051 to 1.750 for k = 4, and from 2.249 to 2.157 for k = 5. The approximation ratio for k = 3 surprisingly achieves the same value as in the splittable case. Our techniques, such as EX-ITP - an extension of the classic ITP method, have the potential to improve algorithms for other routing problems as well.
Cite as

Jingyang Zhao and Mingyu Xiao. Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 93:1-93:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhao_et_al:LIPIcs.MFCS.2025.93,
  author =	{Zhao, Jingyang and Xiao, Mingyu},
  title =	{{Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{93:1--93:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.93},
  URN =		{urn:nbn:de:0030-drops-242008},
  doi =		{10.4230/LIPIcs.MFCS.2025.93},
  annote =	{Keywords: Combinatorial Optimization, Capacitated Vehicle Routing, Approximation Algorithms, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.12
Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework

Authors: Sang Won Bae, Nicolau Oliver, and Evanthia Papadopoulou

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a set S of n colored sites, each s ∈ S associated with a distance-to-site function δ_s : ℝ² → ℝ, we consider two distance-to-color functions for each color: one takes the minimum of δ_s for sites s ∈ S in that color and the other takes the maximum. These two sets of distance functions induce two families of higher-order Voronoi diagrams for colors in the plane, namely, the minimal and maximal order-k color Voronoi diagrams, which include various well-studied Voronoi diagrams as special cases. In this paper, we derive an exact upper bound 4k(n-k)-2n on the total number of vertices in both the minimal and maximal order-k color diagrams for a wide class of distance functions δ_s that satisfy certain conditions, including the case of point sites S under convex distance functions and the L_p metric for any 1 ≤ p ≤ ∞. For the L_1 (or, L_∞) metric, and other convex polygonal metrics, we show that the order-k minimal diagram of point sites has O(min{k(n-k), (n-k)²}) complexity, while its maximal counterpart has O(min{k(n-k), k²}) complexity. To obtain these combinatorial results, we extend the Clarkson-Shor framework to colored objects, and demonstrate its application to several fundamental geometric structures, including higher-order color Voronoi diagrams, colored j-facets, and levels in the arrangements of piecewise linear/algebraic curves/surfaces. We also present iterative algorithms to compute higher-order color Voronoi diagrams.
Cite as

Sang Won Bae, Nicolau Oliver, and Evanthia Papadopoulou. Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bae_et_al:LIPIcs.SoCG.2025.12,
  author =	{Bae, Sang Won and Oliver, Nicolau and Papadopoulou, Evanthia},
  title =	{{Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.12},
  URN =		{urn:nbn:de:0030-drops-231647},
  doi =		{10.4230/LIPIcs.SoCG.2025.12},
  annote =	{Keywords: higher-order Voronoi diagrams, color Voronoi diagrams, Hausdorff Voronoi diagrams, colored j-facets, arrangements, Clarkson-Shor technique}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.62
On Approximability of 𝓁₂² Min-Sum Clustering

Authors: Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, and Samson Zhou

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The 𝓁₂² min-sum k-clustering problem is to partition an input set into clusters C_1,…,C_k to minimize ∑_{i=1}^k ∑_{p,q ∈ C_i} ‖p-q‖₂². Although 𝓁₂² min-sum k-clustering is NP-hard, it is not known whether it is NP-hard to approximate 𝓁₂² min-sum k-clustering beyond a certain factor. In this paper, we give the first hardness-of-approximation result for the 𝓁₂² min-sum k-clustering problem. We show that it is NP-hard to approximate the objective to a factor better than 1.056 and moreover, assuming a balanced variant of the Johnson Coverage Hypothesis, it is NP-hard to approximate the objective to a factor better than 1.327. We then complement our hardness result by giving a fast PTAS for 𝓁₂² min-sum k-clustering. Specifically, our algorithm runs in time O(n^{1+o(1)}d⋅ 2^{(k/ε)^O(1)}), which is the first nearly linear time algorithm for this problem. We also consider a learning-augmented setting, where the algorithm has access to an oracle that outputs a label i ∈ [k] for input point, thereby implicitly partitioning the input dataset into k clusters that induce an approximately optimal solution, up to some amount of adversarial error α ∈ [0,1/2). We give a polynomial-time algorithm that outputs a (1+γα)/(1-α)²-approximation to 𝓁₂² min-sum k-clustering, for a fixed constant γ > 0.
Cite as

Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, and Samson Zhou. On Approximability of 𝓁₂² Min-Sum Clustering. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 62:1-62:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{karthikc.s._et_al:LIPIcs.SoCG.2025.62,
  author =	{Karthik C. S. and Lee, Euiwoong and Rabani, Yuval and Schwiegelshohn, Chris and Zhou, Samson},
  title =	{{On Approximability of 𝓁₂² Min-Sum Clustering}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{62:1--62:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.62},
  URN =		{urn:nbn:de:0030-drops-232142},
  doi =		{10.4230/LIPIcs.SoCG.2025.62},
  annote =	{Keywords: Clustering, hardness of approximation, polynomial-time approximation schemes, learning-augmented algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.49
On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications

Authors: Arnold Filtser

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a metric space (X,d_X), a (β,s,Δ)-sparse cover is a collection of clusters 𝒞 ⊆ P(X) with diameter at most Δ, such that for every point x ∈ X, the ball B_X(x,Δ/β) is fully contained in some cluster C ∈ 𝒞, and x belongs to at most s clusters in 𝒞. Our main contribution is to show that the shortest path metric of every K_r-minor free graphs admits (O(r),O(r²),Δ)-sparse cover, and for every ε > 0, (4+ε,O(1/ε)^r,Δ)-sparse cover (for arbitrary Δ > 0). We then use this sparse cover to show that every K_r-minor free graph embeds into 𝓁_∞^{Õ(1/ε)^{r+1}⋅log n} with distortion 3+ε (resp. into 𝓁_∞^{Õ(r²)⋅log n} with distortion O(r)). Further, among other applications, this sparse cover immediately implies an algorithm for the oblivious buy-at-bulk problem in fixed minor free graphs with the tight approximation factor O(log n) (previously nothing beyond general graphs was known).
Cite as

Arnold Filtser. On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{filtser:LIPIcs.SoCG.2025.49,
  author =	{Filtser, Arnold},
  title =	{{On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.49},
  URN =		{urn:nbn:de:0030-drops-232015},
  doi =		{10.4230/LIPIcs.SoCG.2025.49},
  annote =	{Keywords: Sparse cover, minor free graphs, metric embeddings, 𝓁\underline∞, oblivious buy-at-bulk}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.65
Recognizing 2-Layer and Outer k-Planar Graphs

Authors: Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The crossing number of a graph is the least number of crossings over all drawings of the graph in the plane. Computing the crossing number of a given graph is NP-hard, but fixed-parameter tractable (FPT) with respect to the natural parameter. Two well-known variants of the problem are 2-layer crossing minimization and circular crossing minimization, where every vertex must lie on one of two layers, namely two parallel lines, or a circle, respectively. In both cases, edges are drawn as straight-line segments. Both variants are NP-hard, but admit FPT-algorithms with respect to the natural parameter. In recent years, in the context of beyond-planar graphs, a local version of the crossing number has also received considerable attention. A graph is k-planar if it admits a drawing with at most k crossings per edge. In contrast to the crossing number, recognizing k-planar graphs is NP-hard even if k = 1 and hence not likely to be FPT with respect to the natural parameter k. In this paper, we consider the two above variants in the local setting. The k-planar graphs that admit a straight-line drawing with vertices on two layers or on a circle are called 2-layer k-planar and outer k-planar graphs, respectively. We study the parameterized complexity of the two recognition problems with respect to the natural parameter k. For k = 0, the two classes of graphs are exactly the caterpillars and outerplanar graphs, respectively, which can be recognized in linear time. Two groups of researchers independently showed that outer 1-planar graphs can also be recognized in linear time [Hong et al., Algorithmica 2015; Auer et al., Algorithmica 2016]. One group asked explicitly whether outer 2-planar graphs can be recognized in polynomial time. Our main contribution consists of XP-algorithms for recognizing 2-layer k-planar graphs and outer k-planar graphs, which implies that both recognition problems can be solved in polynomial time for every fixed k. We complement these results by showing that recognizing 2-layer k-planar graphs is XNLP-complete and that recognizing outer k-planar graphs is XNLP-hard. This implies that both problems are W[t]-hard for every t and that it is unlikely that they admit FPT-algorithms. On the other hand, we present an FPT-algorithm for recognizing 2-layer k-planar graphs where the order of the vertices on one layer is specified.
Cite as

Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff. Recognizing 2-Layer and Outer k-Planar Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.SoCG.2025.65,
  author =	{Kobayashi, Yasuaki and Okada, Yuto and Wolff, Alexander},
  title =	{{Recognizing 2-Layer and Outer k-Planar Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.65},
  URN =		{urn:nbn:de:0030-drops-232170},
  doi =		{10.4230/LIPIcs.SoCG.2025.65},
  annote =	{Keywords: 2-layer k-planar graphs, outer k-planar graphs, recognition algorithms, local crossing number, bandwidth, FPT, XNLP, XP, W\lbrackt\rbrack}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.73
Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position

Authors: Anastasiia Tkachenko and Haitao Wang

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Given a set P of n points in the plane, its unit-disk graph G(P) is a graph with P as its vertex set such that two points of P are connected by an edge if their (Euclidean) distance is at most 1. We consider several classical problems on G(P) in a special setting when points of P are in convex position. These problems are all NP-hard in the general case. We present efficient algorithms for these problems under the convex position assumption. ● For the problem of finding the smallest dominating set of G(P), we present an O(knlog n) time algorithm, where k is the smallest dominating set size. We also consider the weighted case in which each point of P has a weight and the goal is to find a dominating set in G(P) with minimum total weight; our algorithm runs in O(n³log² n) time. In particular, for a given k, our algorithm can compute in O(kn²log² n) time a minimum weight dominating set of size at most k (if it exists). ● For the discrete k-center problem, which is to find a subset of k points in P (called centers) for a given k, such that the maximum distance between any point in P and its nearest center is minimized. We present an algorithm that solves the problem in O(min{n^{4/3}log n+knlog² n,k² nlog²n}) time, which is O(n²log² n) in the worst case when k = Θ(n). For comparison, the runtime of the current best algorithm for the continuous version of the problem where centers can be anywhere in the plane is O(n³ log n). ● For the problem of finding a maximum independent set in G(P), we give an algorithm of O(n^{7/2}) time and another randomized algorithm of O(n^{37/11}) expected time, which improve the previous best result of O(n⁶log n) time. Our algorithms can be extended to compute a maximum-weight independent set in G(P) with the same time complexities when points of P have weights. - If we are looking for an (unweighted) independent set of size 3, we derive an algorithm of O(nlog n) time; the previous best algorithm runs in O(n^{4/3}log² n) time (which works for the general case where points of P are not necessarily in convex position). - If points of P have weights and are not necessarily in convex position, we present an algorithm that can find a maximum-weight independent set of size 3 in O(n^{5/3+δ}) time for an arbitrarily small constant δ > 0. By slightly modifying the algorithm, a maximum-weight clique of size 3 can also be found within the same time complexity. ● For the dispersion problem, which is to find a subset of k points from P for a given k, such that the minimum pairwise distance of the points in the subset is maximized. We present an algorithm of O(n^{7/2}log n) time and another randomized algorithm of O(n^{37/11}log n) expected time, which improve the previous best result of O(n⁶) time. - If k = 3, we present an algorithm of O(nlog² n) time and another randomized algorithm of O(nlog n) expected time; the previous best algorithm runs in O(n^{4/3}log² n) time (which works for the general case where points of P are not necessarily in convex position).
Cite as

Anastasiia Tkachenko and Haitao Wang. Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{tkachenko_et_al:LIPIcs.STACS.2025.73,
  author =	{Tkachenko, Anastasiia and Wang, Haitao},
  title =	{{Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{73:1--73:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.73},
  URN =		{urn:nbn:de:0030-drops-228982},
  doi =		{10.4230/LIPIcs.STACS.2025.73},
  annote =	{Keywords: Dominating set, k-center, geometric set cover, independent set, clique, vertex cover, unit-disk graphs, convex position, dispersion, maximally separated sets}
}
  • Refine by Type
  • 17 Document/PDF
  • 15 Document/HTML

  • Refine by Publication Year
  • 6 2026
  • 9 2025
  • 1 2021
  • 1 2018

  • Refine by Author
  • 3 Schwiegelshohn, Chris
  • 2 Bhattacharya, Binay
  • 2 Cohen-Addad, Vincent
  • 2 Higashikawa, Yuya
  • 2 Kameda, Tsunehiko
  • Show More...

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

  • Refine by Classification
  • 9 Theory of computation → Computational geometry
  • 3 Theory of computation → Facility location and clustering
  • 2 Mathematics of computing → Graph algorithms
  • 2 Mathematics of computing → Graph theory
  • 2 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 2 Euclidean space
  • 2 Fine-Grained Complexity
  • 2 evacuation problem
  • 2 k-means clustering
  • 1 1-Planarity
  • 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