We consider data structures for handling streams of check-in and check-out requests, and that must identify the set of check-ins that are not matched by a corresponding check-out. We show that, if this set has size k, it is possible to handle this problem in space O(k log n) by a deterministic data structure. However, if check-outs may occur that do not match any check-in, then no low-space deterministic solution is possible; instead, we provide a randomized solution with near-optimal space and high probability of answering queries correctly.
We show how to test whether a graph is a partial cube, and if so embed it isometrically into a hypercube, in time O(n2), improving previous O(nm)-time solutions; here n is the number of vertices and m is the number of edges. The ideas are to use bit-parallelism to speed up previous approaches to the embedding step, and to verify that the resulting embedding is isometric using an all-pairs shortest path algorithm from "algorithms for media".
Greedy drawing is an idea for encoding network routing tables into the geometric coordinates of an embedding of the network, but most previous work in this area has ignored the space complexity of these encoded tables. We refine a method of R. Kleinberg for embedding arbitrary graphs into the hyperbolic plane, which uses linearly many bits to represent each vertex, and show that only logarithmic bits per point are needed.
We investigate isometric embeddings of other graphs into Fibonacci cubes, graphs formed from the families of fixed-length bitstrings with no two consecutive ones.
We consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media. Among all drawings of this type, we show how to find the one with optimal angular resolution. The solution involves a transformation from the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles.
Shows that, when the tight span of a finite metric space is homeomorphic to a subset of the plane, it has the geometry of a Manhattan orbifold and can be constructed in time linear in the size of the input distance matrix. As a consequence, it can be tested in the same time whether a metric space is isometric to a subset of the L1 plane.
Suppose that P is the intersection of n halfspaces in D dimensions, but that the bounded faces of P are at most d-dimensional, for some d that is much smaller than D. Then in this case we show that the number of vertices of P is O(nd), independent of D. We also investigate related bounds on the number of bounded faces of all dimensions of P, and algorithms for efficiently listing the vertices and bounded faces of P.
We study the combinatorial complexity of generalized Voronoi diagrams that determine the closest two point sites to a query point, where the distance from the query point to a pair of sites is a combination of the individual distances to the sites and the distance from one site in the pair to the other.
We experiment with our degeneracy-based algorithm for listing maximal cliques in sparse graphs and show that it works well on large graphs drawn from several repositories of real-world social networks and bioinformatics networks.
For the journal version, see "Listing all maximal cliques in large sparse real-world graphs in near-optimal time", which combines results from this and a different conference paper.
We study the recursive partitions of rectangles into sets of rectangles, and partitions of those rectangles into smaller rectangles, to form stylized visualizations of hierarchically subdivided geographic regions. There are several variations of varying difficulty depending on how much of the geographic information from the input we require the output to preserve.
We apply competitive analysis to the problem of deciding online which cell phone tower to change to when a phone moves out of the coverage region of the tower it is connected to. We show that, when the coverage regions have constant ply (at most a constant number of them overlap any point of the plane) it is possible to get within a constant factor of the minimum possible number of handovers that an offline algorithm could achieve.
We determine the symmetric difference between two similar sets of items, held by different machines on the internet, using an amount of communication bandwidth that is proportional only to the difference between the sets and with low computational overhead. Our solution technique combines the invertible Bloom filter data structure from our previous work on streaming straggler detection with a randomized sampling scheme that allows us to accurately and efficiently estimate the size of the difference.
We investigate greedy routing schemes for social networks, in which participants know categorical information about some other participants and use it to guide message delivery by forwarding messages to neighbors that have more categories in common with the eventual destination. We define the membership dimension of such a scheme to be the maximum number of categories that any individual belongs to, a natural measure of the cognitive load of greedy routing on its participants. And we show that membership dimension is closely related to the small world phenomenon: a social network can be given a category system with polylogarithmic membership dimension that supports greedy routing if, and only if, the network has polylogarithmic diameter.
We show that a partial order has a non-crossing upward planar drawing if and only if it has order dimension two, and we use the Dedekind-MacNeille completion to find a drawing with the minimum possible number of confluent junctions.
We show that, for several variants of the problem of compacting a grid drawing of a graph to use the minimum number of rows or minimum area, no good approximation algorithm is possible. We also develop fixed-parameter tractable algorithms and approximation algorithms showing that some of our inapproximability bounds are tight. See the journal version, "Inapproximability of orthogonal compaction", for some improvements and corrections.
We extend Lombardi drawing (in which each edge is a circular arc and the edges incident to a vertex must be equally spaced around it) to drawings in which edges are composed of multiple arcs, and we investigate the graphs that can be drawn in this more relaxed framework.
The Bellman–Ford algorithm for single-source shortest paths in graphs that may have negatively weighted edges but no negative cycles can be sped up by a technique of Yen in which the graph is partitioned into two directed acyclic subgraphs and edge relaxations alternate between these two subgraphs. We show that choosing this partition randomly gains an additional factor of 2/3 in running time.
Years – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.