727 citations
- University of California, Santa BarbaraUS18 papers
- University of California, BerkeleyUS10 papers
- California Institute of TechnologyUS6 papers
- ETH ZurichCH5 papers
- Princeton UniversityUS5 papers
- University of Maryland, College ParkUS5 papers
- Board of the Swiss Federal Institutes of TechnologyCH4 papers
- Microsoft Research (United Kingdom)GB4 papers
- University of British ColumbiaCA4 papers
- University of California, Los AngelesUS4 papers
- Courant Institute of Mathematical SciencesUS3 papers
- Eindhoven University of TechnologyNL3 papers
Showing 2007 · cs.DSShow all
3 papers · 2 filters
cs.DS2007
A Partition-Based Relaxation For Steiner Trees
Jochen Konemann, David Pritchard, Kunlun Tan
The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G…
cs.DS2007
Data Structures for Mergeable Trees
Loukas Georgiadis, Haim Kaplan, Nira Shafrir +2
Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant requires merging two…
cs.DS2007★ 13 cited
A Local Algorithm for Finding Dense Subgraphs
Reid Andersen
We present a local algorithm for finding dense subgraphs of bipartite graphs, according to the definition of density proposed by Kannan and Vinay. Our algorithm takes as input a bi…