25 citations · 47 across the 6 of their papers we have counts for
9 papers
Quadratic Time Algorithms Appear to be Optimal for Sorting Evolving Data
Juan Jose Besa, William E. Devanny, David Eppstein +2
We empirically study sorting in the evolving data model. In this model, a sorting algorithm maintains an approximation to the sorted order of a list of data items while simultaneou…
Optimally Sorting Evolving Data
Juan Jose Besa, William E. Devanny, David Eppstein +2
We give optimal sorting algorithms in the evolving data framework, where an algorithm's input data is changing while the algorithm is executing. In this framework, instead of produ…
Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs
Giordano Da Lozzo, William E. Devanny, David Eppstein +1
A square-contact representation of a planar graph maps vertices in to interior-disjoint axis-aligned squares in the plane and edges in to adjacencies between the…
Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection
Juan José Besa Vial, William E. Devanny, David Eppstein +1
We study various versions of the problem of scheduling platoons of autonomous vehicles through an unregulated intersection, where an algorithm must schedule which platoons should w…
Parallel Equivalence Class Sorting: Algorithms, Lower Bounds, and Distribution-Based Analysis
William E. Devanny, Michael T. Goodrich, Kristopher Jetviroj
We study parallel comparison-based algorithms for finding all equivalence classes of a set of elements, where sorting according to some total order is not possible. Such scenar…
Track Layouts, Layered Path Decompositions, and Leveled Planarity
Michael J. Bannister, William E. Devanny, Vida Dujmović +2
We investigate two types of graph layouts, track layouts and layered path decompositions, and the relations between their associated parameters track-number and layered pathwidth.…