Algorithms and Computation

Reaching a goal with directional uncertainty.- Constructing degree-3 spanners with other sparseness properties.- Remembering conflicts in history yields dynamic algorithms.- Coloring random graphs in polynomial expected time.- Graphical degree sequence problems with connectivity requirements.- How to treat delete requests in semi-online problems.- Finding the shortest watchman route in a simple polygon.- Constructing shortest watchman routes by divide-and-conquer.- A graph coloring result and its consequences for some guarding problems.- The maximum k-dependent and f-dependent set problem.- Finding shortest non-crossing rectilinear paths in plane regions.- Treewidth of circle graphs.- A framework for constructing heap-like structures in-place.- Double-ended binomial queues.- A simple balanced search tree with O(1) worst-case update time.- Mapping dynamic data and algorithm structures into product networks.- Permutation routing on reconfigurable meshes.- Adaptive and oblivious algorithms for d-cube permutation routing.- On quadratic lattice approximations.- A 2/3-approximation of the matroid matching problem.- Using fractal geometry for solving divide-and-conquer recurrences.- Simple combinatorial Gray codes constructed by reversing sublists.- Time space tradeoffs (getting closer to the barrier?).- Separating exponentially ambiguous NFA from polynomially ambiguous NFA.- Threshold computation and cryptographic security.- On the Power of reading and writing simultaneously in parallel computations.- Relativizing complexity classes with Random Oracles.- An introduction to perpetual gossiping.- A probabilistic selection network with butterfly networks.- Optimal group gossiping in hypercubes under wormhole routing model.- Optimal linear broadcast routing with capacity limitations.- Multicommodity flows: A survey of recent research.- Parallel construction of canonical ordering and convex drawing of triconnected planar graphs.- Number theory helps line detection in digital images an extended abstract.- Optimally computing the shortest weakly visible subedge of a simple polygon preliminary version.- Multicommodity flows in even, planar networks.- Linear time algorithms for disjoint Two-Face Paths Problems in planar graphs.- Robot mapping: Foot-prints vs tokens.- Recent developments on the approximability of combinatorial problems.- On the relationship among cryptographic physical assumptions.- Separating complexity classes related to bounded alternating ?-branching programs.- The complexity of the optimal variable ordering problems of shared binary decision diagrams.- On Horn envelopes and hypergraph transversals.- Page migration algorithms using work functions.- Memory paging for connectivity and path problems in graphs.- Randomized competitive algorithms for successful and unsuccessful search on self-adjusting linear lists.- Randomized on-line algorithms for the page replication problem.- New algorithms for minimizing the longest wire length during circuit compaction.- Parallel algorithms for single-layer channel routing.- Consecutive interval query and dynamic programming on intervals.- An improved algorithm for the traveler's problem.- Vehicle scheduling on a tree with release and handling times.- Scheduling algorithms for a chain-like task system.- Weighted independent perfect domination on cocomparability graphs.- Plane sweep algorithms for the polygonal approximation problems with applications.- Optimal rectilinear steiner tree for extremal point sets.- Faster approximation algorithms for the rectilinear steiner tree problem.