Excluded minors, network decomposition, and multicommodity flow

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Excluded minors, network decomposition, and multicommodity flow

Full text

Pdf (742 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 682 - 690

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Philip Klein
Serge A. Plotkin
Satish Rao

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 73, Citation Count: 41

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167261 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Fast constructions of sparse neighborhood covers. In Proc. l Oth Annual ACM Symposium on Principles of Distributed Computing, 1992.
	2	B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network Decomposition and Locality in Distributed Computation, In Proc. 30th IEEE Annual Symposium on Foundations of Computer Science, pages 364-369, 1989.
	3	Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
	4	Baruch Awerbuch , Amotz Bar Noy , Nathan Linial , David Peleg, Improved routing strategies with succinct tables, Journal of Algorithms, v.11 n.3, p.307-341, Sep. 1990 [doi>10.1016/0196-6774(90)90017-9]
	5	Baruch Awerbuch and David Peleg. Network synchronization with polylogarithmic overhead. In Proc. 31st IEEEAnnual Symposium on Foundations of Computer Science, pages 514-522, 1990.
	6	Sandeep N. Bhatt and Tom Leighton. A framework for solving VLSI layout problems, f Comp. and Syst. Sci., 28(2):300-343, April 1984.
	7	E Hias, A. Feinstein, and C.E. Shannon. A note on the maximum flow through a network. IRS Trans. Information Theory, 2:117-119, 1956.
	8	L. R. Ford, Jr. and D. R. Fulkerson. Maximal Flow Through a Network. Canadian Journal af Math., 8:399-404, 1956.
	9	Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate max-flow min-(multi)cut theorems and their applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.698-707, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167266]
	10	E N. Klein, S. Rao, A. Agrawal, and R. Ravi. An approximate max-flow min-cut relation for multicommodity flow, with applications. Submitted to Combinatorica (1992). Preliminary version appeared as "Approximation through multicommodity flow," In Proc. 31 th IEEEAnnual Symposium on Foundations of Computer Science, pages 726-727, 1990.
	11	T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proc. 29th IEEE Annual Symposium on Faundatiam of Computer Science, pages 422-431, 1988.
	12	Nathan Linial , Michael Saks, Decomposing graphs into regions of small diameter, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.320-330, January 28-30, 1991, San Francisco, California, United States
	13	H. Okamura and I.D. Seymour. Multicommodity flows in planar graphs, f Combinatorial Theory (B), 31:75-81, 1981.
	14	David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
	15	Serge A. Plotkin , Éva Tardos, Improved bounds on the max-flow min-cut ratio for multicommodity flows, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.691-697, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167263]
	16	ED. Seymour. Matroids and multicommodity flows. EuropeanJournalofCombinatorics, 2:257-290, 1981.
	17	Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
	18	Spyros Tragoudas, VLSI partitioning approximation algorithms based on multicommodity flow and other techniques, University of Texas at Dallas, Richardson, TX, 1991

CITED BY 41

	Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States
	Serge Plotkin , Satish Rao , Warren D. Smith, Shallow excluded minors and improved graph decompositions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.462-470, January 23-25, 1994, Arlington, Virginia, United States
	Christos Kaklamanis , Danny Krizanc , Satish Rao, New graph decompositions and fast emulations in hypercubes and butterflies, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.325-334, June 30-July 02, 1993, Velen, Germany
	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999
	Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States
	Satish Rao , Andréa W. Richa, New approximation techniques for some ordering problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.211-218, January 25-27, 1998, San Francisco, California, United States
	Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate max-flow min-(multi)cut theorems and their applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.698-707, May 16-18, 1993, San Diego, California, United States
	Ilan Newman , Yuri Rabinovich, A lower bound on the distortion of embedding planar metrics into Euclidean space, Proceedings of the eighteenth annual symposium on Computational geometry, p.94-96, June 05-07, 2002, Barcelona, Spain
	Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation algorithms for the 0-extension problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.8-16, January 07-09, 2001, Washington, D.C., United States
	Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Yuri Rabinovich, On average distortion of embedding metrics into the line and into L₁, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Yigal Bejerano , Nicole Immorlica , Joseph (Seffi) Naor , Mark Smith, Efficient location area planning for personal communication systems, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
	Erik D. Demaine , Fedor V. Fomin , MohammadTaghi Hajiaghayi , Dimitrios M. Thilikos, Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Erik D. Demaine , MohammadTaghi Hajiaghayi, Equivalence of local treewidth and linear local treewidth and its algorithmic applications, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Aaron Archer , Jittat Fakcharoenphol , Chris Harrelson , Robert Krauthgamer , Kunal Talwar , Éva Tardos, Approximate classification via earthmover metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	David R. Karger, Using random sampling to find maximum flows in uncapacitated undirected graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.240-249, May 04-06, 1997, El Paso, Texas, United States
	Nathan Linial , Avner Magen , Assaf Naor, Girth and euclidean distortion, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Eyal Amir , Robert Krauthgamer , Satish Rao, Constant factor approximation of vertex-cuts in planar graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Marcin Bienkowski , Miroslaw Korzeniowski , Harald Räcke, A practical algorithm for constructing oblivious routing schemes, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Gruia Calinescu , Cristina G. Fernandes , Bruce Reed, Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width, Journal of Algorithms, v.48 n.2, p.333-359, September 2003
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004
	Kenji Obata, Approximate max-integral-flow/min-multicut theorems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Robert Krauthgamer , James R. Lee, The intrinsic dimensionality of graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Mohammad T. Hajiaghayi , Robert Kleinberg , Tom Leighton, Improved lower and upper bounds for universal TSP in planar metrics, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.649-658, January 22-26, 2006, Miami, Florida
	Eyal Amir , Sheila McIlraith, Partition-based logical reasoning for first-order and propositional theories, Artificial Intelligence, v.162 n.1-2, p.49-88, February 2005
	Uriel Feige , MohammadTaghi Hajiaghayi , James R. Lee, Improved approximation algorithms for minimum-weight vertex separators, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Erik D. Demaine , Fedor V. Fomin , Mohammadtaghi Hajiaghayi , Dimitrios M. Thilikos, Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs, Journal of the ACM (JACM), v.52 n.6, p.866-893, November 2005
	Yuval Emek , David Peleg, A tight upper bound on the probabilistic embedding of series-parallel graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1045-1053, January 22-26, 2006, Miami, Florida
	Christina Fragouli , Tarik Tabet, On conditions for constant throughput in wireless networks, ACM Transactions on Sensor Networks (TOSN), v.2 n.3, p.359-379, August 2006
	Yigal Bejerano , Mark A. Smith , Joseph Naor , Nicole Immorlica, Efficient location area planning for personal communication systems, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.438-450, April 2006
	Erik D. Demaine , Dotan Emanuel , Amos Fiat , Nicole Immorlica, Correlation clustering in general weighted graphs, Theoretical Computer Science, v.361 n.2, p.172-187, 1 September 2006
	Ken-ichi Kawarabayashi , Bojan Mohar, Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Udi Wieder, Strong-diameter decompositions of minor free graphs, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Uriel Feige , James R. Lee, An improved approximation ratio for the minimum linear arrangement problem, Information Processing Letters, v.101 n.1, p.26-29, 16 January 2007
	Robert Krauthgamer , Tim Roughgarden, Metric clustering via consistent labeling, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.809-818, January 20-22, 2008, San Francisco, California
	T-H. Hubert Chan , Anupam Gupta , Kunal Talwar, Ultra-low-dimensional embeddings for doubling metrics, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.333-342, January 20-22, 2008, San Francisco, California
	Costas Busch , Ryan LaFortune , Srikanta Tirthapura, Improved sparse covers for graphs excluding a fixed minor, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Glencora Borradaile , James R. Lee , Anastasios Sidiropoulos, Randomly removing g handles at once, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	James R. Lee , Anastasios Sidiropoulos, On the geometry of graphs with a forbidden minor, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Shirish S. Karande , Zheng Wang , Hamid R. Sadjadpour , J. J. Garcia-Luna-Aceves, Optimal unicast capacity of random geometric graphs: impact of multipacket transmission and reception, IEEE Journal on Selected Areas in Communications, v.27 n.7, p.1180-1191, September 2009