Vertex cuts, random walks, and dimension reduction in series-parallel graphs

DOI10.1145/1250790.1250882zbMath1232.68163DBLPconf/stoc/BrinkmanKL07OpenAlexW2086904111WikidataQ58198039 ScholiaQ58198039MaRDI QIDQ3549664

James R. Lee, Adriana Karagiozova, Bo Brinkman

Publication date: 5 January 2009

Published in: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1250790.1250882

zbMATH Keywords

random walksdimension reductionseries-parallel graphsvertex cutsshortest-path metrics

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (7)

Coarse differentiation and multi-flows in planar graphs ⋮ Markov type and threshold embeddings ⋮ An introduction to the Ribe program ⋮ Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs ⋮ Spectral calculus and Lipschitz extension for barycentric metric spaces ⋮ A node-capacitated Okamura-Seymour theorem ⋮ Multicommodity flows and cuts in polymatroidal networks

This page was built for publication: Vertex cuts, random walks, and dimension reduction in series-parallel graphs