DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.34

Minimum Link Fencing

Authors: Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract

We study a variant of the geometric multicut problem, where we are given a set 𝒫 of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where 𝒫 contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of 𝒫⧵{Q} does not intersect Q.

Cite as

Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu. Minimum Link Fencing. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ISAAC.2022.34,
  author =	{Bhore, Sujoy and Klute, Fabian and L\"{o}ffler, Maarten and N\"{o}llenburg, Martin and Terziadis, Soeren and Villedieu, Ana\"{i}s},
  title =	{{Minimum Link Fencing}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.34},
  URN =		{urn:nbn:de:0030-drops-173191},
  doi =		{10.4230/LIPIcs.ISAAC.2022.34},
  annote =	{Keywords: computational geometry, polygon nesting, polygon separation}
}

Document

DOI: 10.4230/LIPIcs.ESA.2022.44

Turbocharging Heuristics for Weak Coloring Numbers

Authors: Alexander Dobler, Manuel Sorge, and Anaïs Villedieu

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract

Bounded expansion and nowhere-dense classes of graphs capture the theoretical tractability for several important algorithmic problems. These classes of graphs can be characterized by the so-called weak coloring numbers of graphs, which generalize the well-known graph invariant degeneracy (also called k-core number). Being NP-hard, weak-coloring numbers were previously computed on real-world graphs mainly via incremental heuristics. We study whether it is feasible to augment such heuristics with exponential-time subprocedures that kick in when a desired upper bound on the weak coloring number is breached. We provide hardness and tractability results on the corresponding computational subproblems. We implemented several of the resulting algorithms and show them to be competitive with previous approaches on a previously studied set of benchmark instances containing 86 graphs with up to 183831 edges. We obtain improved weak coloring numbers for over half of the instances.

Cite as

Alexander Dobler, Manuel Sorge, and Anaïs Villedieu. Turbocharging Heuristics for Weak Coloring Numbers. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.ESA.2022.44,
  author =	{Dobler, Alexander and Sorge, Manuel and Villedieu, Ana\"{i}s},
  title =	{{Turbocharging Heuristics for Weak Coloring Numbers}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.44},
  URN =		{urn:nbn:de:0030-drops-169820},
  doi =		{10.4230/LIPIcs.ESA.2022.44},
  annote =	{Keywords: Structural sparsity, parameterized algorithms, parameterized complexity, fixed-parameter tractability}
}

Search Results

Documents authored by Villedieu, Anaïs

Minimum Link Fencing

Abstract

Cite as

Turbocharging Heuristics for Weak Coloring Numbers

Abstract

Cite as

Thanks for your feedback!

Could not send message