A representation of cuts witihin 6/5 times the edge connectivity with applications

by András A. Benczúr

Proc. 34th Annual Symp. on Found. of Comp. Sci. (1995) ps.gz ps pdf

Versions of the document #1 #2 #3 in Citeseer database

Reference in context as in the Hypertext Bibliography Project (apparently not maintained since 1998)

Related articles

The paper appears in a refereed version in my Ph.D. Thesis

A very preliminary (don't blame me--I told you) version appeared as "On the structure of near-minimum edge cuts", Tech. report MIT/LCS/TR-639 (1994) ps.gz ps pdf

Citations

1. Oded Goldreich and Dana Ron.
   Property testing in bounded degree graphs.
   Algorithmica 32 (2):302-343 (2002)
2. Dinitz Y, Nossenson R
   Incremental maintenance of the 5-edge-connectivity classes of a graph
   LECT NOTES COMPUT SC 1851: 272-285 2000
3. David R Karger
   Minimum Cuts in Near-Linear Time
   Draft journal version of STOC 96
4. Denis Naddef, Stefan Thienel,
   Efficient Separation Routines for the Symmetric Traveling Salesman Problem I: General Tools and Comb Separation
5. Oded Goldreich and Dana Ron
   Property testing in bounded degree graphs
   Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 406-415, El Paso, Texas, 4-6 May 1997.
6. Hiroshi Nagamochi and Toshihide Ibaraki
   Deterministic O (nm) time edge-splitting in undirected graphs
   Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pages 64-73, Philadelphia, Pennsylvania, 22-24 May 1996.