4 citations · 23 across the 22 of their papers we have counts for
5 papers · 1 filter
Good -divisions Imply Optimal Amortised Decremental Biconnectivity
Jacob Holm, Eva Rotenberg
We present a data structure that, given a graph of vertices and edges, and a suitable pair of nested -divisions of , preprocesses in time and handles…
Decremental SPQR-trees for Planar Graphs
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz +2
We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over operation…
Compressed Communication Complexity of Longest Common Prefixes
Philip Bille, Mikko Berggreen Ettienne, Roberto Grossi +2
We consider the communication complexity of fundamental longest common prefix (Lcp) problems. In the simplest version, two parties, Alice and Bob, each hold a string, and ,…
String Attractors: Verification and Optimization
Dominik Kempa, Alberto Policriti, Nicola Prezza +1
String attractors [STOC 2018] are combinatorial objects recently introduced to unify all known dictionary compression techniques in a single theory. A set is a…
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann +5
We consider very natural "fence enclosure" problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set of points in th…