You are in : Home » Results & submissions » Select UOA » 11 - Computer Science and Informatics » View submission: University of Warwick » Outputs » Detail

Output details

11 - Computer Science and Informatics

University of Warwick

Return to search Previous output Next output

Output 49 of 99 in the submission

Article title

Estimating the weight of metric minimum spanning trees in sublinear time

Type

D - Journal article

DOI

10.1137/060672121

Title of journal

SIAM Journal on Computing

Article number

Volume number

Issue number

First page of article

904

ISSN of journal

1095-7111

Year of publication

2009

URL

http://epubs.siam.org/doi/abs/10.1137/060672121

Number of additional authors

Additional information

<12> Published in one of the top two journals in the field, this paper presents the first (1+epsilon)-approximation sublinear-time algorithm for the classical optimisation problem of estimating the cost of a minimum-spanning tree in metric graphs. Preliminary results on this topic appeared at STOC; this paper is a major extension of that work. This result and the associated techniques have been cited as a major development in sublinear algorithms (Chazelle, Princeton; Indyk, MIT; Onak, IBM; Rubinfeld, MIT; Shapira, Tel-Aviv). This research formed the foundation for the Advances in Sublinear Algorithms project (EPSRC EP/G064679/1, 2009-2013), ranked 1 by the evaluation panel.

Interdisciplinary

Cross-referral requested

Research group

T - Theory and Foundations

Citation count

Proposed double-weighted

Double-weighted statement

Reserve for a double-weighted output

Non-English

English abstract