Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Vertex sparsifiers : new results from old techniques

Tools
- Tools
+ Tools

Englert, Matthias, Gupta, A., Krauthgamer, Robert, Räcke, Harald, Talgam-Cohen, Inbal and Talwar, Kunal (2010) Vertex sparsifiers : new results from old techniques. In: Serna, Maria and Shaltiel, Ronen and Jansen, Klaus and Rolim, José, (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science (6302). Springer Verlag, pp. 152-165. ISBN 9783642153686

[img] Text
fulltext17.pdf - Published Version
Embargoed item. Restricted access to Repository staff only

Download (234Kb)
Official URL: http://dx.doi.org/10.1007/978-3-642-15369-3_12

Request Changes to record.

Abstract

Given a capacitated graph G = (V,E) and a set of terminals K ⊆ V, how should we produce a graph H only on the terminals K so that every (multicommodity) flow between the terminals in G could be supported in H with low congestion, and vice versa? (Such a graph H is called a flow-sparsifier for G.) What if we want H to be a “simple” graph? What if we allow H to be a convex combination of simple graphs?
Improving on results of Moitra [FOCS 2009] and Leighton and Moitra [STOC 2010], we give efficient algorithms for constructing: (a) a flow-sparsifier H that maintains congestion up to a factor of ${\smash{O(\frac{\log k}{\log \log k})}}$, where k = |K|. (b) a convex combination of trees over the terminals K that maintains congestion up to a factor of O(logk). (c) for a planar graph G, a convex combination of planar graphs that maintains congestion up to a constant factor. This requires us to give a new algorithm for the 0-extension problem, the first one in which the preimages of each terminal are connected in G. Moreover, this result extends to minor-closed families of graphs.Our bounds immediately imply improved approximation guarantees for several terminal-based cut and ordering problems.

Item Type: Book Item
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Computer terminals, Graph algorithms
Series Name: Lecture Notes in Computer Science
Publisher: Springer Verlag
ISBN: 9783642153686
Book Title: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Editor: Serna, Maria and Shaltiel, Ronen and Jansen, Klaus and Rolim, José
Official Date: 2010
Dates:
DateEvent
2010Published
Number: 6302
Page Range: pp. 152-165
DOI: 10.1007/978-3-642-15369-3_12
Status: Not Peer Reviewed
Publication Status: Published
Description:
Funder: Engineering and Physical Sciences Research Council (EPSRC), University of Warwick. Centre for Discrete Mathematics and Its Applications
Version or Related Resource: Conference paper. http://wrap.warwick.ac.uk/id/eprint/4700
Related URLs:
  • Related item in WRAP

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us