Detecting cycles in dynamic graphs in polynomial time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Detecting cycles in dynamic graphs in polynomial time

Full text

Pdf (820 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twentieth annual ACM symposium on Theory of computing table of contents

Chicago, Illinois, United States

Pages: 398 - 406

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

S. Rao Kosaraju	Dept. of Computer Science, Johns Hopkins Univ., Baltimore, MD
Gregory Sullivan	Dept. of Computer Science, Johns Hopkins Univ., Baltimore, MD

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 22, Citation Count: 10

Additional Information:

abstract 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/62212.62251 What is a DOI?

ABSTRACT

Consider a digraph which has labels on its edges which are k-dimensional vectors. In this paper we show it is possible in polynomial time to determine if such a digraph contains a zero cycle, i.e., a cycle whose edge labels sum to the zero vector component-wise. This solves the open problem of finding cycles in dynamic graphs which was posed by Iwano and Steiglitz. Our solution has a time complexity of &Ogr;(|V| log(|V|)Z) where Z is the complexity of a linear programming problem. For the important cases of two and three dimensions we present &Ogr;(Z) time algorithms. The linear programming problems we solve have at most 2|E| variables and &Ogr;(|E| + |V| + k) constraints.

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	K. iw~no and K. Steiglitz. Optimization of one. bit full adder~ embedded in regular structures. IEEE Transactions on Acoustics, Speech, and Si~gnal Processing, 1289- 1300, 1986.
	2	K. Iwano , K. Steiglitz, Testing for cycles in infinite graphs with periodic structure, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.46-55, January 1987, New York, New York, United States [doi>10.1145/28395.28401]
	3	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
	4	J. Orlin. Some problems on dynamic / periodic graphs. In W. R. Pulleyblank, editor, Progress in Combinatorial Optimization, pages 273-293, Academic Press, Orlando, Florida, 1984.
	5	P. M. Vaidya, An algorithm for linear programming which requires O(((m+n)n^z+(m+n)¹n)) arithmetic operations, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.29-38, January 1987, New York, New York, United States [doi>10.1145/28395.28399]

CITED BY 10

	Edith Cohen , Nimrod Megiddo, Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs, Journal of the ACM (JACM), v.40 n.4, p.791-830, Sept. 1993
	Muralidharan Kodialam , James B. Orlin, Recognizing strong connectivity in (dynamic) periodic graphs and its relation to integer programming, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.131-135, January 28-30, 1991, San Francisco, California, United States
	L. Thiele , K. Strehl , D. Ziegenbein , R. Ernst , J. Teich, FunState—an internal design representation for codesign, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.558-565, November 07-11, 1999, San Jose, California, United States
	E. Cohen , N. Megiddo, Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.523-534, May 14-17, 1989, Seattle, Washington, United States
	V. P. Roychowdhury , T. Kailath, Study of parallelism in regular iterative algorithms, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.367-376, July 02-06, 1990, Island of Crete, Greece
	Franz Höfting , Egon Wanke, Polynomial algorithms for minimum cost paths in periodic graphs, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.493-499, January 25-27, 1993, Austin, Texas, United States
	Wolfgang Backes , Uwe Schwiegelshohn , Lothar Thiele, Analysis of free schedule in periodic graphs, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.333-342, June 29-July 01, 1992, San Diego, California, United States
	Nelson Luiz Passos , Edwin Hsing-Mean Sha, Achieving Full Parallelism Using Multidimensional Retiming, IEEE Transactions on Parallel and Distributed Systems, v.7 n.11, p.1150-1163, November 1996
	Michael Sheliga , Nelson Luiz Passos , Edwin Hsing-Mean S' ha, Fully Parallel Hardware/Software Codesign for Multi-Dimensional DSP Applications, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.18, March 18-20, 1996
	Uwe Schwiegelshohn , Lothar Thiele, Dynamic Min-Max Problems, Discrete Event Dynamic Systems, v.9 n.2, p.111-134, May 1999