Fully dynamic algorithms for chordal graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fully dynamic algorithms for chordal graphs

Full text

Pdf (221 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 923 - 924

Year of Publication: 1999

ISBN:0-89871-434-6

Author

Louis Ibarra

Dept. of Computer Science, University of Victoria, Victoria, BC, Canada V8W 3P6

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 34, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

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

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	J. R. S. Blair and B. Peyton. An introduction to chordal graphs and clique trees. In Graph Theory and Sparse Matrix Computation, pages 1-29. Springer- Verlag, New" York, 1993. IMA Vol. 56.
	2	P. Buneman. A characterization of rigid circuit graphs. Discrete Math, 9:205-212, 1974.
	3	F. Chin and D. Houri<. Algorithms for updating spanning trees. Journal of Computer and System Sciences. 16:333-344, 1978.
	4	Anders Edenbrandt, Chordal graph recognition is in NC, Information Processing Letters, v.24 n.4, p.239-241, March 1987 [doi>10.1016/0020-0190(87)90140-2]
	5	David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997 [doi>10.1145/265910.265914]
	6	Yossi Shiloach , Shimon Even, An On-Line Edge-Deletion Problem, Journal of the ACM (JACM), v.28 n.1, p.1-4, Jan. 1981 [doi>10.1145/322234.322235]
	7	J. Feigenbaum and S. Kannan. Dynamic graph algorithms. In Handbook of Discrete and Combinatorial Mathematics. CRC Press, Boca Raton, FL. To appear.
	8	G. N. Frederickson. Data structures for on-line updating of minimum spamfing trees, with applications. SIAM Journal on Computing. 14(4):781-798. 1985.
	9	D. Fulkerson and O. Gross. Incidence matrices and interval graphs. Pacific Journal of Mathematics. 15(3):835-855. 1965.
	10	F. Gavril. An algorithm for testing chordality of graphs. Information Processing Letters, 3(4):110-112, 1972.
	11	M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York. 1980.
	12	Monika Rauch Henzinger , Valerie King, Randomized dynamic graph algorithms with polylogarithmic time per operation, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.519-527, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225269]
	13	Monika Rauch Henzinger , Valerie King, Maintaining Minimum Spanning Trees in Dynamic Graphs, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.594-604, July 07-11, 1997
	14	Monika Rauch Henzinger , Mikkel Thorup, Improved Sampling with Applications to Dynamic Graph Algorithms, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.290-299, July 08-12, 1996
	15	Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.79-89, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276715]
	16	Joseph Naor , Moni Naor , Alejandro A. Schäffer, Fast parallel algorithms for chordal graphs, SIAM Journal on Computing, v.18 n.2, p.327-349, April 1989 [doi>10.1137/0218023]
	17	C. H. Papadimitriou and M. Yannakakis. Scheduling interval-ordered tasks. SIAM Journal on Computing, 8(3):405-409, 1979.
	18	John H. Reif, A topological approach to dynamic graph connectivity, Information Processing Letters, v.25 n.1, p.65-70, 20 April 1987 [doi>10.1016/0020-0190(87)90095-0]
	19	D. J. Rose, R. E. Tarjan, and G. S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2):266-283, 1976.
	20	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	21	P. M. Spira and A. Pan. On finding and updating spanning trees and shortest paths. SIAM Journal on Computing, 4(3):375-380, 1975.
	22	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	23	Robert E. Tarjan , Mihalis Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, v.13 n.3, p.566-579, August 1984 [doi>10.1137/0213035]

CITED BY 4

	Ron Shamir , Roded Sharan, A fully dynamic algorithm for modular decomposition and recognition of cographs, Discrete Applied Mathematics, v.136 n.2-3, p.329-340, 15 February 2004
	C. Crespelle , C. Paul, Fully dynamic recognition algorithm and certificate for directed cograph, Discrete Applied Mathematics, v.154 n.12, p.1722-1741, 15 July 2006
	Pinar Heggernes , Charis Papadopoulos, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, Theoretical Computer Science, v.410 n.1, p.1-15, January, 2009
	Pinar Heggernes , Federico Mancini, Dynamically maintaining split graphs, Discrete Applied Mathematics, v.157 n.9, p.2057-2069, May, 2009