David Eppstein - Publications

Miscellanous graph theory

• Parallel algorithmic techniques for combinatorial computation.
  D. Eppstein and Z. Galil.
  Ann. Rev. Comput. Sci. 3:233-283, 1988.
  Invited talk by Z. Galil, 16th Int. Coll. Automata, Languages and Programming, Stresa, Italy, 1989.
  Lecture Notes in Comp. Sci. 372, 1989, pp. 304-318, © Springer-Verlag.

  This survey on parallel algorithms emphasized the use of basic subroutines such as prefix sums, Euler tours, ear decomposition, and matrix multiplication for solving more complicated graph problems.

  (BibTeX -- Citations -- CiteSeer -- ACM DL (ARCS) -- ACM DL (ICALP))

• Parallel recognition of series parallel graphs.
  D. Eppstein.
  Information & Computation 98:41-55, 1992.

  Characterizes two-terminal series graphs in terms of a tree-like structure in their ear decompositions. Uses this characterization to construct parallel algorithms that recognize these graphs and construct their series-parallel decompositions.

  (BibTeX -- Citations -- MIT hypertext bibliography -- CiteSeer -- ACM DL)

• Efficient sequential and parallel algorithms for computing recovery points in trees and paths.
  M. Chrobak, D. Eppstein, G.F. Italiano, and M. Yung.
  2nd ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1991, pp. 158-167.
  ALCOM Report 91-74, University of Rome, 1991.

  Described slightly superlinear algorithms for partitioning a tree into a given number of subtrees, making them all as short as possible. Frederickson at the same conference further improved the sequential time to linear. There may still be something worth publishing in the parallel algorithms.

  (BibTeX -- Citations)

• Clustering for faster network simplex pivots.
  D. Eppstein.
  Tech. Rep. 93-19, ICS, UCI, 1993.
  5th ACM-SIAM Symp. Discrete Algorithms, Arlington, 1994, pp. 160-166.
  Networks 35(3):173-180, 2000.

  Speeds up the worst case time per pivot for various versions of the network simplex algorithm for minimum cost flow problems. Uses techniques from dynamic graph algorithms as well as some simple geometric data structures.

  (BibTeX -- CiteSeer)

• Minimum range balanced cuts via dynamic subset sums.
  D. Eppstein.
  Tech. Rep. 95-10, ICS, UCI, 1995.
  J. Algorithms 23:375-385, 1997.

  Describes data structures for maintaining the solution of a dynamically changing subset sum problem, and uses them to find a cut in a graph minimizing the difference between the heaviest and lightest cut edge.

  (BibTeX -- ACM DL)

• The weighted maximum-mean subtree and other bicriterion subtree problems.
  J. Carlson and D. Eppstein.
  arxiv:cs.CG/0503023.
  Proc. 10th Scand. Worksh. Algorithm Theory (SWAT 2006).
  Lecture Notes in Comp. Sci. 4059, 2005, pp. 397-408.

  We give a linear time algorithm for pruning a node-weighted tree to maximize the average node weight of the pruned subtree; this problem was previously studied under the less obvious name "The Fractional Prize-Collecting Steiner Tree Problem on Trees".

  (BibTeX)

• Interconnect criticality driven delay relaxation.
  L. Singhal, E. Bozorgzadeh, and D. Eppstein.
  IEEE Trans. CAD 26(10):1803-1817, 2007.

  We consider a problem of assigning delays to components in a circuit so that each component is part of a critical path, but the number of edges belonging to critical paths is minimized. We show the problem to be NP-complete via a reduction from finding independent dominating sets in bipartite graphs minimizing dominated edges, and give experimental results on heuristics.

Graph Theory -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.