Clique partitions, graph compression and speeding-up algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Clique partitions, graph compression and speeding-up algorithms

Full text

Pdf (1.18 MB)

Source

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

New Orleans, Louisiana, United States

Pages: 123 - 133

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Tomás Feder	Bellcore, Morristown, NJ
Rajeev Motwani	Stanford Univ., Stanford, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 68, Citation Count: 13

Additional Information:

references cited by index terms review 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/103418.103424 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.

	Bl	Norbert Blum, A new approach to maximum matching in general graphs, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.586-597, July 1990, Warwick University, England
	CHM	J. Cheriyan, T. Hagerup and K. Mehlhorn, "Fast and Simple Network Flow Algorithms," Preprint, 1990.
	CT	Joseph Cheriyan , Ramakrishna Thurimella, Algorithms for parallel k-vertex connectivity and sparse certificates, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.391-401, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103460]
	Di	E.A. Dinic, "Algorithm for solution of a problem of maximum flow in a network with power estimation," Soviet Math. Doklady, vol. 11 (1970), pp. 1277-1280.
	ES	P. Erdos and J. H. Spencer, Probabilistic Methods in Combinatorics. Academic Press, 1974.
	Ev	S. Even, "An algorithm for determining whether the connectivity of a graph is at least k," SIAM Journal on Computing, vol. 4 (1975), pp. 393-396.
	ET	S. Even and 1#. E. Tarjan, "Network flow and testing graph connectivity," SIAM Journal on Computing, vol. 4 (1975), pp. 507-518.
	Fe	T. Feder, "2-Satisfiability and Network Flow," submitted to Algorithm#ca.
	Fr	M.L. Fredman, "New bounds on the complexity of the shortest path problems," SIAM Journal on Computing, vol. 5 (1976), pp. 83- 89.
	Ga	Z. Galil, "Finding the Vertex Connectivity of Graphs," SIAM Journal on Co#npuiing, vol. 9 (1980), pp. 197-199.
	GRS	R.L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey Theory. John Wiley & Sons, 1980.
	Ho	I. Holyer, "The NP-completeness of some edge partitioning problems," SIAM Journal on Computing, vol. 10 (1981), pp. 713-717.
	HK	J.E. Hopcroft and R. M. Karp, "An O(n#12) algorithm for maximum matchings in bipartite graphs," SIAM journal on Computing, vol. 2 (1973), pp. 225-231.
	Ma	D.W. Matula, "Determining Edge Connectivity in O(nm)," Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, (1987), pp. 249-251.
	MNN	Rajeev Motwani , Joseph Seffi Naor , Moni Naor, The probabilistic method yields deterministic parallel algorithms, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.478-516, December 1994, Research Triangle Park, North Carolina, United States
	MV	S. Micali and V. Vazirani, "An O(IVI~#. IE{) Algorithm for Finding Maximum Matchings in General Graphs," Proceedings of the 21st IEEE Symposium on Foundations of Computer Science, (1980), pp. 17-27.
	Na	M. Naor, Succinct representation of general unlabeled graphs, Discrete Applied Mathematics, v.28 n.3, p.303-307, Sep. 1990 [doi>10.1016/0166-218X(90)90011-Z]
	NI	H. Nagamochi and T. Ibaraki, "Linear Time Algorithms for Finding a Sparse k- Connected Spanning Subgraph of a k- Connected Graph," A lgorithmica, to appear.
	Ra	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	Ro	F. Romani, "Shortest-path problem is not harder than matrix multiplication," Information Processing Letters, vol. 11 (1980), pp. 134-136.
	Sp	.1. Spencer, Ten lectures on the probabilistic method. SIAM (Philadelphia), 1987.
	Tu	G. Turan, "On the Succinct Representation of Graphs," Discrete Applied Mathematics, vol. 8 (1984), pp. 289-294.
	Za	K. Zarankiewicz, Problem P. 101, Colloq. Math., vol. 2 (1951), p. 301.

CITED BY 13

	Raimund Seidel, On the all-pairs-shortest-path problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.745-749, May 04-06, 1992, Victoria, British Columbia, Canada
	Kasturi R. Varadarajan , Pankaj K. Agarwal, Approximation algorithms for bipartite and non-bipartite matching in the plane, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.805-814, January 17-19, 1999, Baltimore, Maryland, United States
	Paul J. Heffernan , Stefan Schirra, Approximate decision algorithms for point set congruence, Proceedings of the eighth annual symposium on Computational geometry, p.93-101, June 10-12, 1992, Berlin, Germany
	D. Aingworth , C. Chekuri , R. Motwani, Fast estimation of diameter and shortest paths (without matrix multiplication), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.547-553, January 28-30, 1996, Atlanta, Georgia, United States
	Rajeev Motwani, Average-case analysis of algorithms for matchings and related problems, Journal of the ACM (JACM), v.41 n.6, p.1329-1356, Nov. 1994
	Kasturi R. Varadarajan, Approximating monotone polygonal curves using the uniform metric, Proceedings of the twelfth annual symposium on Computational geometry, p.311-318, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Boris V. Cherkassky , Andrew V. Goldberg , Paul Martin , Joao C. Setubal , Jorge Stolfi, Augment or push: a computational study of bipartite matching and unit-capacity flow algorithms, Journal of Experimental Algorithmics (JEA), 3, p.8-es, 1998
	Frank Gurski , Egon Wanke, Vertex disjoint paths on clique-width bounded graphs, Theoretical Computer Science, v.359 n.1, p.188-199, 14 August 2006
	Parke Godfrey , Jarek Gryz, View disassembly: A rewrite that extracts portions of views, Journal of Computer and System Sciences, v.73 n.6, p.941-961, September, 2007
	Shuo Zhou , Yi Zhu , Yuanfang Hu , Ronald Graham , Mike Hutton , Chung-Kuan Cheng, Timing model reduction for hierarchical timing analysis, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Timothy M. Chan, More algorithms for all-pairs shortest paths in weighted graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Clémence Magnien , Matthieu Latapy , Michel Habib, Fast computation of empirically tight bounds for the diameter of massive graphs, Journal of Experimental Algorithmics (JEA), 13, February 2009
	Joshua Spiegel , Neoklis Polyzotis, TuG synopses for approximate query answering, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-56, April 2009

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.2 Graph Theory
Subjects: Graph algorithms

Additional Classification:
E. Data
E.1 DATA STRUCTURES
Subjects: Graphs and networks
E.4 CODING AND INFORMATION THEORY
Subjects: Data compaction and compression

General Terms:
Algorithms, Theory

REVIEW

"Hans J. Schneider : Reviewer"

The idea of this paper is to speed up some graph algorithms by using a compressed representation of the graph. This representation is constructed by partitioning the graph into bipartite cliques, each of which is replaced by a tree. The number more...

Collaborative Colleagues:

Tomás Feder: colleagues

Rajeev Motwani: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player