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

DOI10.1145/153724.153727zbMath0782.68053OpenAlexW2026261955MaRDI QIDQ4271085

Nimrod Megiddo, Edith Cohen

Publication date: 24 February 1994

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/153724.153727

zbMATH Keywords

treesgraph algorithmsperiodic graphscombinatorial algorithmapplication of multidimensional searchapplication of parametric methodpaths and circuit problemrecurrences and difference equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Hyperplane separation technique for multidimensional mean-payoff games ⋮ Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies ⋮ Powers of matrices over an extremal algebra with applications to periodic graphs ⋮ Topologically trivial closed walks in directed surface graphs ⋮ Polynomial time analysis of toroidal periodic graphs ⋮ Optimization with additional variables and constraints ⋮ Unnamed Item ⋮ NEW RESULTS ON COMPUTABILITY OF RECURRENCE EQUATIONS ⋮ Algorithms and complexity analysis for some flow problems

This page was built for publication: Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs