Modularity of cycles and paths in graphs
- 1 April 1991
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 38 (2) , 255-274
- https://doi.org/10.1145/103516.103517
Abstract
Certain problems related to the length of cycles and paths modulo a given integer are studied. Linear-time algorithms are presented that determine whether all cycles in an undirected graph are of length P mod Q and whether all paths between two specified nodes are of length P mod Q , for fixed integers P . Q . These results are compared to those for directed graphs.Keywords
This publication has 6 references indexed in Scilit:
- On path lengths modulo threeJournal of Graph Theory, 1991
- The directed subgraph homeomorphism problemTheoretical Computer Science, 1980
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- Computing a graph's period quadratically by node condensationDiscrete Mathematics, 1973
- Qualitative Economics and the Scope of the Correspondence PrincipleEconometrica, 1968
- The Scope of Qualitative EconomicsThe Review of Economic Studies, 1962