Arrow Research search

Author name cluster

David Eppstein

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

51 papers
2 author rows

Possible papers

51

TCS Journal 2022 Journal Article

On the treewidth of Hanoi graphs

  • David Eppstein
  • Daniel Frishberg
  • William Maxwell

The objective of the well-known Tower of Hanoi puzzle is to move a set of discs one at a time from one of a set of pegs to another, while keeping the discs sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.

Details DOI

TCS Journal 2020 Journal Article

Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect

  • Jean Cardinal
  • Erik D. Demaine
  • David Eppstein
  • Robert A. Hearn
  • Andrew Winslow

We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary operations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration, sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE-completeness of the following decision problems: • Given two satisfying assignments of a planar monotone instance of NAE 3-SAT, can one assignment be transformed into the other by a sequence of variable flips such that the formula remains satisfied at every step? • Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum? • Given two points in { 0, 1 } n contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n-hypercube connecting the two points and contained in P? These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the sets of instances that appear as input to the reconfiguration problems in our reductions lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length.

Details DOI

SODA Conference 2019 Conference Paper

Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time

  • David Eppstein
  • Bruce A. Reed

We consider decomposing a 3-connected planar graph G using laminar separators of size three. We show how to find a maximal set of laminar 3-separators in such a graph in linear time. We also discuss how to find maximal laminar set of 3-separators from special families. For example we discuss non-trivial cuts, ie. cuts which split G into two components of size at least two. For any vertex v, we also show how to find a maximal set of 3-separators disjoint from v which are laminar and satisfy: every vertex in a separator X has two neighbours not in the unique component of G – X containing v. In all cases, we show how to construct a corresponding tree decomposition of adhesion three. Our new algorithms form an important component of recent methods for finding disjoint paths in nonplanar graphs.

Details

SODA Conference 2016 Conference Paper

Treetopes and their Graphs

  • David Eppstein

We define treetopes, a generalization of the three-dimensional roofless polyhedra (Halin graphs) to arbitrary dimensions. Like roofless polyhedra, treetopes have a designated base facet such that every face of dimension greater than one intersects the base in more than one point. We prove an equivalent characterization of the 4-treetopes using the concept of clustered planarity from graph drawing, and we use this characterization to recognize the graphs of 4-treetopes in polynomial time. This result provides one of the first classes of 4-polytopes, other than pyramids and stacked polytopes, that can be recognized efficiently from their graphs.

Details

SODA Conference 2015 Conference Paper

Minimum Forcing Sets for Miura Folding Patterns

  • Brad Ballinger
  • Mirela Damian
  • David Eppstein
  • Robin Y. Flatland
  • Jessica Ginepro
  • Thomas C. Hull

We introduce the study of forcing sets in mathematical origami. The origami material folds flat along straight line segments called creases, each of which is assigned a folding direction of mountain or valley. A subset F of creases is forcing if the global folding mountain/valley assignment can be deduced from its restriction to F. In this paper we focus on one particular class of foldable patterns called Miura-ori, which divide the plane into congruent parallelograms using horizontal lines and zigzag vertical lines. We develop efficient algorithms for constructing a minimum forcing set of a Miura-ori map, and for deciding whether a given set of creases is forcing or not. We also provide tight bounds on the size of a forcing set, establishing that the standard mountain-valley assignment for the Miura-ori is the one that requires the most creases in its forcing sets. Additionally, given a partial mountain/valley assignment to a subset of creases of a Miura-ori map, we determine whether the assignment domain can be extended to a locally flat-foldable pattern on all the creases. At the heart of our results is a novel correspondence between flat-foldable Miura-ori maps and 3-colorings of grid graphs.

Details

TCS Journal 2013 Journal Article

Category-based routing in social networks: Membership dimension and the small-world phenomenon

  • David Eppstein
  • Michael T. Goodrich
  • Maarten Löffler
  • Darren Strash
  • Lowell Trott

A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as “he is a prominent lawyer in Boston” or “she is a Freshman sociology major at Harvard”). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon.

Details DOI

SODA Conference 2013 Conference Paper

Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges

  • Michael J. Bannister
  • Christopher DuBois
  • David Eppstein
  • Padhraic Smyth

We consider the problem of analyzing social network data sets in which the edges of the network have timestamps, and we wish to analyze the subgraphs formed from edges in contiguous subintervals of these timestamps. We provide data structures for these problems that use near-linear preprocessing time, linear space, and sublogarithmic query time to handle queries that ask for the number of connected components, number of components that contain cycles, number of vertices whose degree equals or is at most some predetermined value, number of vertices that can be reached from a starting set of vertices by time-increasing paths, and related queries.

Details

TCS Journal 2012 Journal Article

Extended dynamic subgraph statistics using h -index parameterized data structures

  • David Eppstein
  • Michael T. Goodrich
  • Darren Strash
  • Lowell Trott

We present techniques for maintaining subgraph frequencies in a dynamic graph, using data structures that are parameterized in terms of h, the h -index of the graph. Our methods extend previous results of Eppstein and Spiro for maintaining statistics for undirected subgraphs of size three to directed subgraphs and to subgraphs of size four. For the directed case, we provide a data structure to maintain counts for all 3-vertex induced subgraphs in O ( h ) amortized time per update. For the undirected case, we maintain the counts of size-four subgraphs in O ( h 2 ) amortized time per update. These extensions enable a number of new applications in Bioinformatics and Social Networking research.

Details DOI

IROS Conference 2012 Conference Paper

UOBPRM: A uniformly distributed obstacle-based PRM

  • Hsin-Yi Yeh
  • Shawna L. Thomas
  • David Eppstein
  • Nancy M. Amato

This paper presents a new sampling method for motion planning that can generate configurations more uniformly distributed on C-obstacle surfaces than prior approaches. Here, roadmap nodes are generated from the intersections between C-obstacles and a set of uniformly distributed fixed-length segments in C-space. The results show that this new sampling method yields samples that are more uniformly distributed than previous obstacle-based methods such as OBPRM, Gaussian sampling, and Bridge test sampling. UOBPRM is shown to have nodes more uniformly distributed near C-obstacle surfaces and also requires the fewest nodes and edges to solve challenging motion planning problems with varying narrow passages.

Details

SODA Conference 2010 Conference Paper

Paired Approximation Problems and Incompatible Inapproximabilities

  • David Eppstein

This paper considers pairs of optimization problems that are defined from a single input and for which it is desired to find a good approximation to either one of the problems. In many instances, it is possible to efficiently find an approximation of this type that is better than known inapproximability lower bounds for either of the two individual optimization problems forming the pair. In particular, we find either a (1 + ∊)-approximation to (1, 2)-TSP or a 1/∊-approximation to maximum independent set, from a given graph, in linear time. We show a similar paired approximation result for finding either a coloring or a long path. However, no such tradeoff exists in some other cases: for set cover and hitting set problems defined from a single set family, and for clique and independent set problems on the same graph, it is not possible to find an approximation when both problems are combined that is better than the best approximation for either problem on its own.

Details

SODA Conference 2009 Conference Paper

Linear-time algorithms for geometric graphs with sublinearly many crossings

  • David Eppstein
  • Michael T. Goodrich
  • Darren Strash

We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O ( n ) time on connected geometric graphs having n vertices and k crossings, where k is smaller than n by an iterated logarithmic factor. Specific problems we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeroes in” on edge crossings, together with methods for extending planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having n segments and k crossings in linear time, for the case when k is sublinear in n by an iterated logarithmic factor.

Details

SODA Conference 2009 Conference Paper

Self-overlapping curves revisited

  • David Eppstein
  • Elena Mumford

Let S be a surface embedded in space in such a way that each point has a neighborhood within which the surface is a terrain. Then S projects to an immersed surface in the plane, the boundary of which is a (possibly self-intersecting) curve. Under what circumstances can we reverse these mappings algorithmically? Shor and van Wyk considered one such problem, determining whether a curve is the boundary of an immersed disk; they showed that the self-overlapping curves defined in this way can be recognized in polynomial time. We show that several related problems are more difficult: it is NP-complete to determine whether an immersed disk is the projection of a disk embedded in space, or whether a curve is the boundary of an immersed surface in the plane that is not constrained to be a disk. However, when a casing is supplied with a self-intersecting curve, describing which component of the curve lies above and which below at each crossing, we may determine in time linear in the number of crossings whether the cased curve forms the projected boundary of a surface in space. As a related result, we show that an immersed surface with a single boundary curve that crosses itself n times has at most 2 n /2 combinatorially distinct spatial embeddings, and we discuss the existence of fixed-parameter tractable algorithms for related problems.

Details

FOCS Conference 1999 Conference Paper

Setting Parameters by Example

  • David Eppstein

We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution; the task is to determine parameter values that lead to the given solution. We describe algorithms for solving such problems for minimum spanning trees, shortest paths, and other "optimal subgraph" problems, and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.

Details

FOCS Conference 1998 Conference Paper

Parametric and Kinetic Minimum Spanning Trees

  • Pankaj K. Agarwal
  • David Eppstein
  • Leonidas J. Guibas
  • Monika Henzinger

We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter /spl lambda/ and wish to compute the sequence of minimum spanning trees generated as /spl lambda/ varies. We also consider the kinetic minimum spanning tree problem, in which /spl lambda/ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n/sup 2/3/log/sup 4/3/) per combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup 1/2/log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for planar graphs with weight changes but no insertions or deletions.

Details

FOCS Conference 1995 Conference Paper

3-Coloring in Time O(1. 3446 n ): A No-MIS Algorithm

  • Richard Beigel
  • David Eppstein

We consider worst case time bounds for NP-complete problems including 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS. 3-SAT is equivalent to (2, 3)-SSS while the other problems above are special cases of (3, 2)-SSS; there is also a natural duality transformation from (a, b)-SSS to (b, a)-SSS. We give a fast algorithm for (3, 2)-SSS and use it to improve the time bounds for solving the other problems listed above.

Details

FOCS Conference 1994 Conference Paper

Finding the k Shortest Paths

  • David Eppstein

We give algorithms for finding the k shortest paths (not required to be simple) connecting a pair of vertices in a digraph. Our algorithms output an implicit representation of these paths in a digraph with n vertices and m edges, in time O(m+n log n+k). We can also find the k shortest paths from a given source s to each vertex in the graph, in total time O(m+n log n+kn). We describe applications to dynamic programming problems including the knapsack problem, sequence alignment, and maximum inscribed polygons. >

Details

FOCS Conference 1992 Conference Paper

Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees

  • Pankaj K. Agarwal
  • David Eppstein
  • Jirí Matousek 0001

The authors describe dynamic data structures for half-space range reporting and for maintaining the minima of a decomposable function. Using these data structures, they obtain efficient dynamic algorithms for a number of geometric problems, including closest/farthest neighbor searching, fixed dimension linear programming, bi-chromatic closest pair, diameter, and Euclidean minimum spanning tree. >

Details

FOCS Conference 1992 Conference Paper

Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract)

  • David Eppstein
  • Zvi Galil
  • Giuseppe F. Italiano
  • Amnon Nissenzweig

The authors provide data structures that maintain a graph as edges are inserted and deleted, and keep track of the following properties: minimum spanning forests, best swap, graph connectivity, and graph 2-edge-connectivity, in time O(n/sup 1/2/log(m/n)) per change; 3-edge-connectivity, in time O(n/sup 2/3/) per change; 4-edge-connectivity, in time O(n alpha (n)) per change; k-edge-connectivity, in time O(n log n) per change; bipartiteness, 2-vertex-connectivity, and 3-vertex-connectivity, in time O(n log(m/n)) per change; and 4-vertex-connectivity, in time O(n log(m/n)+n alpha (n)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. The algorithms are based on a technique that transforms algorithms for sparse graphs into ones that work on any graph, which they call sparsification. >

Details

FOCS Conference 1991 Conference Paper

Dynamic Three-Dimensional Linear Programming

  • David Eppstein

Linear programming optimizations on the intersection of k polyhedra in R/sup 3/, represented by their outer recursive decompositions, are performed in expected time O(k log k log n+ square root k log k log/sup 3/ n). This result is used to derive efficient algorithms for dynamic linear programming problems ill which constraints are inserted and deleted, and queries must optimize specified objective functions. As an application, an improved solution to the planar 2-center problem, is described. >

Details

TCS Journal 1991 Journal Article

Planar orientations with low out-degree and compaction of adjacency matrices

  • Marek Chrobak
  • David Eppstein

We consider the problem of orienting the edges of a planar graph in such a way that the out-degree of each vertex is minimized. If, for each vertex v, the out-degree is at most d, then we say that such an orientation is d-bounded. We prove the following results: • Each planar graph has a 5-bounded acyclic orientation, which can be constructed in linear time. • Each planar graph has a 3-bounded orientation, which can be constructed in linear time. • A 6-bounded acyclic orientation, and a 3-bounded orientation, of each planar graph can each be constructed in parallel time O(log n log∗ n) on an EREW PRAM, using O(n/log n log∗ n) processors. As an application of these results, we present a data structure such that each entry in the adjacency matrix of a planar graph can be looked up in constant time. The data structure uses linear storage, and can be constructed in linear time.

Details DOI

FOCS Conference 1990 Conference Paper

Provably Good Mesh Generation

  • Marshall W. Bern
  • David Eppstein
  • John R. Gilbert

Several versions of the problem of generating triangular meshes for finite-element methods are studied. It is shown how to triangulate a planar point set or a polygonally bounded domain with triangles of bounded aspect ratio, how to triangulate a planar point set with triangles having no obtuse angles, how to triangulate a point set in arbitrary dimension with simplices of bounded aspect ratio, and how to produce a linear-size Delaunay triangulation of a multidimensional point set by adding a linear number of extra points. All the triangulations have size within a constant factor of optimal and run in optimal time O(n log n+k) with input of size n and output of size k. No previous work on mesh generation simultaneously guarantees well-shaped elements and small total size. >

Details

FOCS Conference 1988 Conference Paper

Speeding up Dynamic Programming

  • David Eppstein
  • Zvi Galil
  • Raffaele Giancarlo

A number of important computational problems in molecular biology, geology, speech recognition, and other areas can be expressed as recurrences which have typically been solved with dynamic programming. By using more sophisticated data structures, and by taking advantage of further structure from the applications, the authors speed up the computation of several of these recurrences by one or two orders of magnitude. The algorithms used are simple and practical. >

Details