Vertex sparsifiers : new results from old techniques
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 5909
- Type
- D - Journal article
- DOI
-
10.1137/130908440
- Title of journal
- SIAM Journal on Computing
- Article number
- -
- First page
- 1239
- Volume
- 43
- Issue
- 4
- ISSN
- 0097-5397
- Open access status
- Out of scope for open access requirements
- Month of publication
- July
- Year of publication
- 2014
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
5
- Research group(s)
-
T - Theory and Foundations
- Citation count
- 14
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- We provide a powerful general framework for generating compact representations of large network graphs. These representations can be used to design improved approximation algorithms for many graph problems. This improves upon a line of work by Leighton (MIT, and CEO of Akamai Technologies) and Moitra (MIT). Our result has been included in the Handbook of Discrete and Computational Geometry and has been utilised by many authors to obtain new results, e.g., by Chuzhoy and Makarychev (Toyota Technological Institute Chicago), Vijayaraghavan (Princeton), Zhou (Carnegie Mellon University), Andoni (Microsoft Research), Chekuri (University of Illinois), Shepherd and Weibel (McGill), Sidiropoulos (Ohio State University).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -