Arrow Research search

Author name cluster

Lars Arge

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.

12 papers
2 author rows

Possible papers

12

SODA Conference 2013 Conference Paper

Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs

  • Freek van Walderveen
  • Norbert Zeh
  • Lars Arge

We revisit I/O-efficient solutions to a number of fundamental problems on planar graphs: single-source shortest paths, topological sorting, and computing strongly connected components. Existing I/O-efficient solutions to these problems pay for I/O efficiency using excessive computation time in internal memory, thereby completely negating the performance gain achieved by minimizing the number of disk accesses. In this paper, we show how to make these algorithms simultaneously efficient in internal and external memory so they achieve I/O complexity O(sort( N )) and take O( N log N ) time in internal memory, where sort( N ) is the number of I/Os needed to sort N items in external memory. The key, and the main technical contribution of this paper, is a multiway version of Miller's simple cycle separator theorem. We show how to compute these separators in linear time in internal memory, and using O(sort( N )) I/Os and O( N log N ) (internal-memory computation) time in external memory.

Details

FOCS Conference 2009 Conference Paper

Orthogonal Range Reporting in Three and Higher Dimensions

  • Peyman Afshani
  • Lars Arge
  • Kasper Green Larsen

In orthogonal range reporting we are to preprocess N points in d-dimensional space so that the points inside a d-dimensional axis-aligned query box can be reported efficiently. This is a fundamental problem in various fields, including spatial databases and computational geometry. In this paper we provide a number of improvements for three and higher dimensional orthogonal range reporting: In the pointer machine model, we improve all the best previous results, some of which have not seen any improvements in almost two decades. In the I/O-model, we improve the previously known three-dimensional structures and provide the first (non-trivial) structures for four and higher dimensions.

Details

FOCS Conference 2006 Conference Paper

Improved Dynamic Planar Point Location

  • Lars Arge
  • Gerth Stølting Brodal
  • Loukas Georgiadis

We develop the first linear-space data structures for dynamic planar point location in general subdivisions that achieve logarithmic query time and poly-logarithmic update time

Details

FOCS Conference 2003 Conference Paper

I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs

  • Lars Arge
  • Norbert Zeh

We present the first I/O-efficient algorithms for the following fundamental problems on directed planar graphs: finding the strongly connected components, finding a simple-path 2/3-separator, and computing a depth-first spanning (DFS) tree. Our algorithms for the first two problems perform O(sort(N)) I/Os, where N = V + E and sort(N) = /spl Theta/((N/B)) is the number of I/Os required to sort N elements. The DFS-algorithm performs O(sort(N) log(N/M)) I/Os, where M is the number of elements that fit into main memory.

Details

STOC Conference 2002 Conference Paper

Cache-oblivious priority queue and graph algorithm applications

  • Lars Arge
  • Michael A. Bender
  • Erik D. Demaine
  • Bryan Holland-Minkley
  • J. Ian Munro

(MATH) In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O ( 1 \over B log M/B N \over B ) amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache-oblivious data structure, M and B are not used in the description of the structure. The bounds match the bounds of several previously developed external-memory (cache-aware) priority queue data structures, which all rely crucially on knowledge about M and B . Priority queues are a critical component in many of the best known external- memory graph algorithms, and using our cache-oblivious priority queue we develop several cache- oblivious graph algorithms.

Details

FOCS Conference 1996 Conference Paper

Optimal Dynamic Interval Management in External Memory (extended abstract)

  • Lars Arge
  • Jeffrey Scott Vitter

The authors present a space- and I/O-optimal external-memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The data structure settles an open problem in databases and I/O algorithms by providing the first optimal external-memory solution to the dynamic interval management problem, which is a special case of 2-dimensional range searching and a central problem for object-oriented and temporal databases and for constraint logic programming. The data structure simultaneously uses optimal linear space (that is, O(N/B) blocks of disk space) and achieves the optimal O(log/sub B/ N+T/B) I/O query bound and O(log/sub B/ N) I/O update bound, where B is the I/O block size and T the number of elements in the answer to a query. The structure is also the first optimal external data structure for a 2-dimensional range searching problem that has worst-case as opposed to amortized update bounds. Part of the data structure uses a novel balancing technique for efficient worst-case manipulation of balanced trees, which is of independent interest.

Details
v2026.09.13