2 Search Results for "Griesbach, Svenja M."

Document
DOI: 10.4230/LIPIcs.ESA.2023.54
Improved Approximation Algorithms for the Expanding Search Problem

Authors: Svenja M. Griesbach, Felix Hommelsheim, Max Klimm, and Kevin Schewior

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
A searcher faces a graph with edge lengths and vertex weights, initially having explored only a given starting vertex. In each step, the searcher adds an edge to the solution that connects an unexplored vertex to an explored vertex. This requires an amount of time equal to the edge length. The goal is to minimize the weighted sum of the exploration times over all vertices. We show that this problem is hard to approximate and provide algorithms with improved approximation guarantees. For the general case, we give a (2e+ε)-approximation for any ε > 0. For the case that all vertices have unit weight, we provide a 2e-approximation. Finally, we provide a PTAS for the case of a Euclidean graph. Previously, for all cases only an 8-approximation was known.
Cite as

Svenja M. Griesbach, Felix Hommelsheim, Max Klimm, and Kevin Schewior. Improved Approximation Algorithms for the Expanding Search Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{griesbach_et_al:LIPIcs.ESA.2023.54,
  author =	{Griesbach, Svenja M. and Hommelsheim, Felix and Klimm, Max and Schewior, Kevin},
  title =	{{Improved Approximation Algorithms for the Expanding Search Problem}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{54:1--54:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.54},
  URN =		{urn:nbn:de:0030-drops-187073},
  doi =		{10.4230/LIPIcs.ESA.2023.54},
  annote =	{Keywords: Approximation Algorithm, Expanding Search, Search Problem, Graph Exploration, Traveling Repairperson Problem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.16
Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages

Authors: Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar and all optimal 2-planar graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs.
Cite as

Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou. Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.SoCG.2020.16,
  author =	{Bekos, Michael A. and Da Lozzo, Giordano and Griesbach, Svenja M. and Gronemann, Martin and Montecchiani, Fabrizio and Raftopoulou, Chrysanthi},
  title =	{{Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.16},
  URN =		{urn:nbn:de:0030-drops-121749},
  doi =		{10.4230/LIPIcs.SoCG.2020.16},
  annote =	{Keywords: Book embeddings, Book thickness, Nonplanar graphs, Planar skeleton}
}
  • Refine by Author
  • 2 Griesbach, Svenja M.
  • 1 Bekos, Michael A.
  • 1 Da Lozzo, Giordano
  • 1 Gronemann, Martin
  • 1 Hommelsheim, Felix
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Approximation Algorithm
  • 1 Book embeddings
  • 1 Book thickness
  • 1 Expanding Search
  • 1 Graph Exploration
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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