86 citations · 243 across the 39 of their papers we have counts for
4 papers · 1 filter
Connectivity Oracles for Planar Graphs
Glencora Borradaile, Seth Pettie, Christian Wulff-Nilsen
We consider dynamic subgraph connectivity problems for planar graphs. In this model there is a fixed underlying planar graph, where each edge and vertex is either "off" (failed) or…
Sharp Bounds on Davenport-Schinzel Sequences of Every Order
Seth Pettie
One of the longest-standing open problems in computational geometry is to bound the lower envelope of univariate functions, each pair of which crosses at most times, for so…
A Resource-Competitive Jamming Defense
Valerie King, Seth Pettie, Jared Saia +1
Consider a scenario where Alice wishes to send a message to Bob in a time-slotted wireless network. However, there exists an adversary, Carol, who aims to prevent the transmiss…
The Locality of Distributed Symmetry Breaking
Leonid Barenboim, Michael Elkin, Seth Pettie +1
Symmetry breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this…