Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs

Full text

Pdf (2.88 MB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 4 (September 1993) table of contents

Pages: 791 - 830

Year of Publication: 1993

ISSN:0004-5411

Authors

Edith Cohen	AT&T Bell Labs, Murray Hill, NJ
Nimrod Megiddo	IBM Almaden Research Center, San Jose, CA; and Tel-Aviv Univ., Tel-Aviv, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/153724.153727 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	K L Clarkson, Linear programming in O(n × 3d2) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986 [doi>10.1016/0020-0190(86)90037-2]
	2	Edith Cohen, Combinatorial algorithms for optimization problems, Stanford University, Stanford, CA, 1992
	3	~COHEN, E., AND MEGIDDO, N. Maximizing concave functions in fixed dimension. Tech. ~Rep. RJ 7656 (71103). IBM Almaden Research Center, San Jose, Calif., Aug. 1990.
	4	Edith Cohen , Nimrod Megiddo, Algorithms and complexity analysis for some flow problems, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.120-130, January 28-30, 1991, San Francisco, California, United States
	5	~COHEN, E., AND MEGIDDO, N. Recognizing properties of periodic graphs. In Applied ~Geometry and Discrete Math. The Victor Klee Festschrtft, vol. 4, P. GrJtzmann and B. ~Sturmfets, eds. ACM, New York, 1991, pp. 135-146.
	6	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	6a	Steven Thomas Cosares , I. Adler, On the complexity of some primal-dual linear programming pairs, 1988
	7	M E Dyer, On a multidimensional search technique and its application to the Euclidean one centre problem, SIAM Journal on Computing, v.15 n.3, p.725-738, August 1986 [doi>10.1137/0215052]
	8	~FARKAS, J. Theorie der einfachen ungleichungen. J. Reme und Angewandte Math. 124 ~(1902), 1-27.
	9	~GROTSCHEL, g,, LOVASZ, L., AND SCHRIJVER, A. Geometric algorithms and combinatorial ~optimization. Springer-Verlag, New York, 1988.
	10	~GRfJNBAUM, B. ConL'expolytopes. Interscience-Wiley, London, 1967.
	11	~IWANO, K. Some problems on doubly periodic infinite graphs. Tech. Rep. CS-TR-078-87. ~Princeton Univ., Princeton, N.J., 1987.
	12	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]
	13	~{WANO, K., AND STEIGLITZ, r. Planarity testing of doubly connected periodic infinite ~graphs. Networks 18 (Oct. 1988), 205-222.
	14	Kazuo Iwano , Kenneth Steiglitz, A semiring on convex polygons and zero-sum cycle problems, SIAM Journal on Computing, v.19 n.5, p.883-901, Oct. 1990 [doi>10.1137/0219061]
	15	~KARP, R.M. A characterization of the minimum cycle mean in a digraph. Disc. Math. 23 ~(1978), 309-311.
	16	Richard M. Karp , Raymond E. Miller , Shmuel Winograd, The Organization of Computations for Uniform Recurrence Equations, Journal of the ACM (JACM), v.14 n.3, p.563-590, July 1967 [doi>10.1145/321406.321418]
	17	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 [doi>10.1145/62212.62251]
	18	George S. Lueker , Nimrod Megiddo , Vijaya Ramachandran, Linear programming with two variables per inequality in poly-log time, SIAM Journal on Computing, v.19 n.6, p.1000-1010, Dec. 1990 [doi>10.1137/0219068]
	19	~MEGIDDO, N. Combinatorial optimization with rational objective functions. Math. Oper. ~Res. 4 (1979), 414-424.
	20	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	21	~MEGIDDO, N. Towards a genuinely polynomial algorithm for linear programming. SIAM J. ~Comput. 12 (1983), 347-353.
	22	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	23	Carolyn Habit Norton , Serge A. Plotkin , Éva Tardos, Using separation algorithms in fixed dimension, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.377-387, January 22-24, 1990, San Francisco, California, United States
	24	~ORLIN, J. B. Some problems in dynamic/periodic graphs. In Progress in combinatorial ~opttmzzation, W. R. Pullyblank, ed. Academic Press, Orlando, Fla., 1984, pp. 273-293.
	25	Vwani Prasad Roychowdhury , Thomas Kailath, Derivation, extensions and parallel implementation of regular iterative algorithms, 1989
	26	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 [doi>10.1145/97444.97704]

CITED BY 3

	Timothy M. Chan, An optimal randomized algorithm for maximum Tukey depth, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994
	Erin W. Chambers , Jeff Erickson , Amir Nayyeri, Homology flows, cohomology cuts, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA

INDEX TERMS

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

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures

G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.1.6 Optimization
Subjects: Linear programming

General Terms:
Algorithms, Theory

Keywords:
application of multidimensional search, application of parametric method, strongly polynomial algorithms periodic graphs

REVIEW

"Stephen Chen : Reviewer"

Consider a directed graph with d -vectors of rational numbers associated with each edge. The problem discussed in this paper is determining whether a cycle whose edge vectors sum to the zero vector e more...

Collaborative Colleagues:

Edith Cohen: colleagues

Nimrod Megiddo: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player