Modularity of Cycles and Paths in Graphs

E. M. Arkin; C. H. Papadimitriou; M. Yannakakis

doi:10.1145/103516.103517

Modularity of Cycles and Paths in Graphs

E. M. Arkin
, C. H. Papadimitriou
, M. Yannakakis

Applied Mathematics and Statistics

Stony Brook University

University of California at San Diego
Nokia

Research output: Contribution to journal › Article › peer-review

31 Scopus citations

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.

Original language	English
Pages (from-to)	255-274
Number of pages	20
Journal	Journal of the ACM (JACM)
Volume	38
Issue number	2
DOIs	https://doi.org/10.1145/103516.103517
State	Published - Jan 4 1991

Keywords

cycles and paths
graphs
modularity

Access to Document

10.1145/103516.103517

Cite this

@article{2c3823cb80db4f1a8550c68604c42202,

title = "Modularity of Cycles and Paths in Graphs",

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 = "cycles and paths, graphs, modularity",

author = "Arkin, \{E. M.\} and Papadimitriou, \{C. H.\} and M. Yannakakis",

year = "1991",

month = jan,

day = "4",

doi = "10.1145/103516.103517",

language = "English",

volume = "38",

pages = "255--274",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

number = "2",

}

TY - JOUR

T1 - Modularity of Cycles and Paths in Graphs

AU - Arkin, E. M.

AU - Papadimitriou, C. H.

AU - Yannakakis, M.

PY - 1991/1/4

Y1 - 1991/1/4

N2 - 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.

AB - 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.

KW - cycles and paths

KW - graphs

KW - modularity

UR - https://www.scopus.com/pages/publications/0041651595

U2 - 10.1145/103516.103517

DO - 10.1145/103516.103517

M3 - Article

SN - 0004-5411

VL - 38

SP - 255

EP - 274

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 2

ER -

Modularity of Cycles and Paths in Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this