Search Results

Documents authored by Kammer, Frank

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.55
Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous

Authors: Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K. Moses Jr.

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Temporal graphs are dynamic graphs where the edge set can change in each time step, while the vertex set stays the same. Exploration of temporal graphs whose snapshot in each time step is a connected graph, called connected temporal graphs, has been widely studied. In this paper, we extend the concept of graph automorphisms from static graphs to temporal graphs and show for the first time that symmetries enable faster exploration: We prove that a connected temporal graph with n vertices and orbit number r (i.e., r is the number of automorphism orbits) can be explored in O(r n^{1+ε}) time steps, for any fixed ε > 0. For r = O(n^c) for constant c < 1, this is a significant improvement over the known tight worst-case bound of Θ(n²) time steps for arbitrary connected temporal graphs. We also give two lower bounds for temporal exploration, showing that Ω(n log n) time steps are required for some inputs with r = O(1) and that Ω(rn) time steps are required for some inputs for any r with 1 ≤ r ≤ n. Moreover, we show that the techniques we develop for fast exploration can be used to derive the following result for rendezvous: Two agents with different programs and without communication ability are placed by an adversary at arbitrary vertices and given full information about the connected temporal graph, except that they do not have consistent vertex labels. Then the two agents can meet at a common vertex after O(n^{1+ε}) time steps, for any constant ε > 0. For some connected temporal graphs with the orbit number being a constant, we also present a complementary lower bound of Ω(nlog n) time steps.
Cite as

Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K. Moses Jr.. Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dogeas_et_al:LIPIcs.ICALP.2024.55,
  author =	{Dogeas, Konstantinos and Erlebach, Thomas and Kammer, Frank and Meintrup, Johannes and Moses Jr., William K.},
  title =	{{Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.55},
  URN =		{urn:nbn:de:0030-drops-201989},
  doi =		{10.4230/LIPIcs.ICALP.2024.55},
  annote =	{Keywords: dynamic graphs, parameterized algorithms, algorithmic graph theory, graph automorphism, orbit number}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2023.37
PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM)

Authors: Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer, and Manuel Penschuck

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
Twin-width (tww) is a parameter measuring the similarity of an undirected graph to a co-graph [Édouard Bonnet et al., 2022]. It is useful to analyze the parameterized complexity of various graph problems. This paper presents two algorithms to compute the twin-width and to provide a contraction sequence as witness. The two algorithms are motivated by the PACE 2023 challenge, one for the exact track and one for the heuristic track. Each algorithm produces a contraction sequence witnessing (i) the minimal twin-width admissible by the graph in the exact track (ii) an upper bound on the twin-width as tight as possible in the heuristic track. Our heuristic algorithm relies on several greedy approaches with different performance characteristics to find and improve solutions. For large graphs we use locality sensitive hashing to approximately identify suitable contraction candidates. The exact solver follows a branch-and-bound design. It relies on the heuristic algorithm to provide initial upper bounds, and uses lower bounds via contraction sequences to show the optimality of a heuristic solution found in some branch.
Cite as

Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer, and Manuel Penschuck. PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM). In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 37:1-37:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{leonhardt_et_al:LIPIcs.IPEC.2023.37,
  author =	{Leonhardt, Alexander and Dell, Holger and Haak, Anselm and Kammer, Frank and Meintrup, Johannes and Meyer, Ulrich and Penschuck, Manuel},
  title =	{{PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM)}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{37:1--37:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.37},
  URN =		{urn:nbn:de:0030-drops-194563},
  doi =		{10.4230/LIPIcs.IPEC.2023.37},
  annote =	{Keywords: PACE 2023 Challenge, Heuristic, Exact, Twin-Width}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.44
Succinct Planar Encoding with Minor Operations

Authors: Frank Kammer and Johannes Meintrup

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Let G be an unlabeled planar and simple n-vertex graph. Unlabeled graphs are graphs where the label-information is either not given or lost during the construction of data-structures. We present a succinct encoding of G that provides induced-minor operations, i.e., edge contractions and vertex deletions. Any sequence of such operations is processed in O(n) time in the word-RAM model. At all times the encoding provides constant time (per element output) neighborhood access and degree queries. Optional hash tables extend the encoding with constant expected time adjacency queries and edge-deletion (thus, all minor operations are supported) such that any number of edge deletions are computed in O(n) expected time. Constructing the encoding requires O(n) bits and O(n) time. The encoding requires ℋ(n) + o(n) bits of space with ℋ(n) being the entropy of encoding a planar graph with n vertices. Our data structure is based on the recent result of Holm et al. [ESA 2017] who presented a linear time contraction data structure that allows to maintain parallel edges and works for labeled graphs, but uses Θ(n log n) bits of space. We combine the techniques used by Holm et al. with novel ideas and the succinct encoding of Blelloch and Farzan [CPM 2010] for arbitrary separable graphs. Our result partially answers the question raised by Blelloch and Farzan whether their encoding can be modified to allow modifications of the graph.
Cite as

Frank Kammer and Johannes Meintrup. Succinct Planar Encoding with Minor Operations. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kammer_et_al:LIPIcs.ISAAC.2023.44,
  author =	{Kammer, Frank and Meintrup, Johannes},
  title =	{{Succinct Planar Encoding with Minor Operations}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.44},
  URN =		{urn:nbn:de:0030-drops-193460},
  doi =		{10.4230/LIPIcs.ISAAC.2023.44},
  annote =	{Keywords: planar graph, r-division, separator, succinct encoding, graph minors}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.62
Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings

Authors: Frank Kammer and Johannes Meintrup

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

Abstract
We present a novel space-efficient graph coarsening technique for n-vertex planar graphs G, called cloud partition, which partitions the vertices V(G) into disjoint sets C of size O(log n) such that each C induces a connected subgraph of G. Using this partition 𝒫 we construct a so-called structure-maintaining minor F of G via specific contractions within the disjoint sets such that F has O(n/log n) vertices. The combination of (F, 𝒫) is referred to as a cloud decomposition. For planar graphs we show that a cloud decomposition can be constructed in O(n) time and using O(n) bits. Given a cloud decomposition (F, 𝒫) constructed for a planar graph G we are able to find a balanced separator of G in O(n/log n) time. Contrary to related publications, we do not make use of an embedding of the planar input graph. We generalize our cloud decomposition from planar graphs to H-minor-free graphs for any fixed graph H. This allows us to construct the succinct encoding scheme for H-minor-free graphs due to Blelloch and Farzan (CPM 2010) in O(n) time and O(n) bits improving both runtime and space by a factor of Θ(log n). As an additional application of our cloud decomposition we show that, for H-minor-free graphs, a tree decomposition of width O(n^{1/2 + ε}) for any ε > 0 can be constructed in O(n) bits and a time linear in the size of the tree decomposition. A similar result by Izumi and Otachi (ICALP 2020) constructs a tree decomposition of width O(k √n log n) for graphs of treewidth k ≤ √n in sublinear space and polynomial time.
Cite as

Frank Kammer and Johannes Meintrup. Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kammer_et_al:LIPIcs.ISAAC.2022.62,
  author =	{Kammer, Frank and Meintrup, Johannes},
  title =	{{Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{62:1--62:15},
  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.62},
  URN =		{urn:nbn:de:0030-drops-173478},
  doi =		{10.4230/LIPIcs.ISAAC.2022.62},
  annote =	{Keywords: planar graph, H-minor-free, space-efficient, separator, tree decomposition}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.141
Two Moves per Time Step Make a Difference

Authors: Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T. Spooner

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex, moves over at most one edge in each time step, visits all vertices, and reaches the last unvisited vertex as early as possible. We show in this paper that every temporal graph with n vertices can be explored in O(n^{1.75}) time steps provided that either the degree of the graph is bounded in each step or the temporal walk is allowed to make two moves per step. This result is interesting because it breaks the lower bound of Omega(n^2) steps that holds for the worst-case exploration time if only one move per time step is allowed and the graph in each step can have arbitrary degree. We complement this main result by a logarithmic inapproximability result and a proof that for sparse temporal graphs (i.e., temporal graphs with O(n) edges in the underlying graph) making O(1) moves per time step can improve the worst-case exploration time at most by a constant factor.
Cite as

Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T. Spooner. Two Moves per Time Step Make a Difference. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 141:1-141:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.ICALP.2019.141,
  author =	{Erlebach, Thomas and Kammer, Frank and Luo, Kelin and Sajenko, Andrej and Spooner, Jakob T.},
  title =	{{Two Moves per Time Step Make a Difference}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{141:1--141:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.141},
  URN =		{urn:nbn:de:0030-drops-107176},
  doi =		{10.4230/LIPIcs.ICALP.2019.141},
  annote =	{Keywords: Temporal Graph Exploration, Algorithmic Graph Theory, NP-Complete Problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.66
Simple 2^f-Color Choice Dictionaries

Authors: Frank Kammer and Andrej Sajenko

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
A c-color choice dictionary of size n in N is a fundamental data structure in the development of space-efficient algorithms that stores the colors of n elements and that supports operations to get and change the color of an element as well as an operation choice that returns an arbitrary element of that color. For an integer f>0 and a constant c=2^f, we present a word-RAM algorithm for a c-color choice dictionary of size n that supports all operations above in constant time and uses only nf+1 bits, which is optimal if all operations have to run in o(n/w) time where w is the word size. In addition, we extend our choice dictionary by an operation union without using more space.
Cite as

Frank Kammer and Andrej Sajenko. Simple 2^f-Color Choice Dictionaries. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kammer_et_al:LIPIcs.ISAAC.2018.66,
  author =	{Kammer, Frank and Sajenko, Andrej},
  title =	{{Simple 2^f-Color Choice Dictionaries}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{66:1--66:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.66},
  URN =		{urn:nbn:de:0030-drops-100141},
  doi =		{10.4230/LIPIcs.ISAAC.2018.66},
  annote =	{Keywords: space efficient, succinct, word RAM}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.65
Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays

Authors: Frank Kammer and Andrej Sajenko

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Many succinct data structures on the word RAM require precomputed tables to start operating. Usually, the tables can be constructed in sublinear time. In this time, most of a data structure is not initialized, i.e., there is plenty of unused space allocated for the data structure. We present a general framework to store temporarily extra buffers between the user defined data so that the data can be processed immediately, stored first in the buffers, and then moved into the data structure after finishing the tables. As an application, we apply our framework to Dodis, Patrascu, and Thorup's data structure (STOC 2010) that emulates c-ary memory and to Farzan and Munro's succinct encoding of arbitrary graphs (TCS 2013). We also use our framework to present an in-place dynamical initializable array.
Cite as

Frank Kammer and Andrej Sajenko. Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kammer_et_al:LIPIcs.MFCS.2018.65,
  author =	{Kammer, Frank and Sajenko, Andrej},
  title =	{{Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.65},
  URN =		{urn:nbn:de:0030-drops-96478},
  doi =		{10.4230/LIPIcs.MFCS.2018.65},
  annote =	{Keywords: space efficiency, succinct c-ary memory, dynamic graph representation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.44
On-the-Fly Array Initialization in Less Space

Authors: Torben Hagerup and Frank Kammer

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We show that for all given n,t,w in {1,2,...} with n<2^w, an array of n entries of w bits each can be represented on a word RAM with a word length of w bits in at most nw+ceil(n(t/(2 w))^t) bits of uninitialized memory to support constant-time initialization of the whole array and O(t)-time reading and writing of individual array entries. At one end of this tradeoff, we achieve initialization and access (i.e., reading and writing) in constant time with nw+ceil(n/w^t) bits for arbitrary fixed t, to be compared with nw+Theta(n) bits for the best previous solution, and at the opposite end, still with constant-time initialization, we support O(log n)-time access with just nw+1 bits, which is optimal for arbitrary access times if the initialization executes fewer than n steps.
Cite as

Torben Hagerup and Frank Kammer. On-the-Fly Array Initialization in Less Space. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 44:1-44:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hagerup_et_al:LIPIcs.ISAAC.2017.44,
  author =	{Hagerup, Torben and Kammer, Frank},
  title =	{{On-the-Fly Array Initialization in Less Space}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{44:1--44:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.44},
  URN =		{urn:nbn:de:0030-drops-82527},
  doi =		{10.4230/LIPIcs.ISAAC.2017.44},
  annote =	{Keywords: data structures, space efficiency, constant-time initialization, on-the-fly initialization, arrays}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.30
Space-Efficient Plane-Sweep Algorithms

Authors: Amr Elmasry and Frank Kammer

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We introduce space-efficient plane-sweep algorithms for basic planar geometric problems. It is assumed that the input is in a read-only array of n items and that the available workspace is Theta(s) bits, where lg n <= s <= n * lg n. Three techniques that can be used as general tools in different space-efficient algorithms are introduced and employed within our algorithms. In particular, we give an almost-optimal algorithm for finding the closest pair among a set of n points that runs in O(n^2 /s + n * lg s) time. We also give a simple algorithm to enumerate the intersections of n line segments that runs in O((n^2 /s^{2/3}) * lg s + k) time, where k is the number of intersections. The counting version can be solved in O((n^2/s^{2/3}) * lg s) time. When the segments are axis-parallel, we give an O((n^2/s) * lg^{4/3} s + n^{4/3} * lg^{1/3} n)-time algorithm that counts the intersections and an O((n^2/s) * lg s * lg lg s + n * lg s + k)-time algorithm that enumerates the intersections, where k is the number of intersections. We finally present an algorithm that runs in O((n^2 /s + n * lg s) * sqrt{(n/s) * lg n}) time to calculate Klee's measure of axis-parallel rectangles.
Cite as

Amr Elmasry and Frank Kammer. Space-Efficient Plane-Sweep Algorithms. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{elmasry_et_al:LIPIcs.ISAAC.2016.30,
  author =	{Elmasry, Amr and Kammer, Frank},
  title =	{{Space-Efficient Plane-Sweep Algorithms}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.30},
  URN =		{urn:nbn:de:0030-drops-68009},
  doi =		{10.4230/LIPIcs.ISAAC.2016.30},
  annote =	{Keywords: closest pair, line-segments intersection, Klee's measure}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.56
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs

Authors: Frank Kammer, Dieter Kratsch, and Moritz Laudahn

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We present space-efficient algorithms for computing cut vertices in a given graph with n vertices and m edges in linear time using O(n+min{m,n log log n}) bits. With the same time and using O(n+m) bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in O(n log log n) time using O(n) bits.
Cite as

Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kammer_et_al:LIPIcs.MFCS.2016.56,
  author =	{Kammer, Frank and Kratsch, Dieter and Laudahn, Moritz},
  title =	{{Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.56},
  URN =		{urn:nbn:de:0030-drops-64683},
  doi =		{10.4230/LIPIcs.MFCS.2016.56},
  annote =	{Keywords: graph algorithms, space efficiency, cut vertices, maximal outerplanar graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.288
Space-efficient Basic Graph Algorithms

Authors: Amr Elmasry, Torben Hagerup, and Frank Kammer

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We reconsider basic algorithmic graph problems in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O(n) bits or little more than that. For computing connected components and performing breadth-first search, we match the running times of standard algorithms that have no memory restrictions, for depth-first search and related problems we come within a factor of \Theta(\log\log n), and for computing minimum spanning forests and single-source shortest-paths trees we come close for sparse input graphs.
Cite as

Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient Basic Graph Algorithms. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 288-301, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{elmasry_et_al:LIPIcs.STACS.2015.288,
  author =	{Elmasry, Amr and Hagerup, Torben and Kammer, Frank},
  title =	{{Space-efficient Basic Graph Algorithms}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{288--301},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.288},
  URN =		{urn:nbn:de:0030-drops-49217},
  doi =		{10.4230/LIPIcs.STACS.2015.288},
  annote =	{Keywords: graph algorithms, depth-first search, single-source shortest paths, register input model}
}
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