Testing for cycles in infinite graphs with periodic structure

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Testing for cycles in infinite graphs with periodic structure

Full text

Pdf (691 KB)

Source

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

New York, New York, United States

Pages: 46 - 55

Year of Publication: 1987

ISBN:0-89791-221-7

Authors

K. Iwano	Dept. of Computer Science, Rinceton University, Plrinceton, NJ
K. Steiglitz	Dept. of Computer Science, Rinceton University, Plrinceton, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 10, Citation Count: 8

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/28395.28401 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	Adam, A. 1961. "On graphs in which two vertices are distinguished," Acta Math. Acad. Sci. Hungary 12, 377-97.
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	Duffin, R. J. 1965. "Topology of seriesparallel networks," Journal of Math Analysis and Applications 10, 303-18.
	4	Guibas, L., L. Ramshaw, J. Stolf 1983. "Kinematic Framework for Computational Geometry," IEEE 24th Symposium of Foundation of Computer Science, 1983.
	5	Iwano K. and K. Steiglitz 1986. "Optimization of one-bit full adders embedded in regular structures," IEEE Transaction on Acoustics, Speech, and Signal Processing, October.
	6	Kallay, M. 1984. "Decomposability of polytopes is a projective invariant," Annals of Discrete Mathematws 20, 191- 96.
	7	Lozano-Perez, T. 1983. "Spatial planning: A configuration space approach," IEEE Trans. on Computer, Feb., 1983.
	8	Kurt Mehlhorn, Graph algorithms and NP-completeness, Springer-Verlag New York, Inc., New York, NY, 1984
	9	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	10	Meyer, W. 1974. "Indecomposable polytopes," Trans. A mer. Math. Soc. 190, 77-86.
	11	Orlin, J. 1984. "Some problems on dynamic/periodic graphs," in Progress in Combinatorial Optimization, 273-93, see Pulleyblank 1984.
	12	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	13	Pulleyblank, W. R. ed. 1984. Progress in Combinatorial Optimization, Academic Press, Orlando, Florida.
	14	Riordan, J. and C. E. Shannon 1942. "The number of two terminal seriesparallel networks," Journal of Math. Physics 21, 83-93.
	15	Shephard, G. C. 1963. "Decomposable convex polyhedron," Mathematika 10, 89-95.
	16	Jacobo Valdes , Robert E. Tarjan , Eugene L. Lawler, The recognition of Series Parallel digraphs, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.1-12, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804393]
	17	Weinberg, L. 1971. "Linear Graphs: theorems, algorithms, and applications," in Aspects of Network and System Theory, R. E. Kalman and N. DeClaris (eds.), Holt, Rinehart, and Winston, N.Y..

CITED BY 8

	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
	Thomas Lengauer , Egon Wanke, Efficient decision procedures for graph properties on context-free graph languages, Journal of the ACM (JACM), v.40 n.2, p.368-393, April 1993
	E. H. -M. Sha , K. Steiglitz, Reconfigurability and Reliability of Systolic/Wavefront Arrays, IEEE Transactions on Computers, v.42 n.7, p.854-862, July 1993
	S. Rao Kosaraju , Gregory Sullivan, Detecting cycles in dynamic graphs in polynomial time, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.398-406, May 02-04, 1988, Chicago, Illinois, United States
	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
	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