Modularity of cycles and paths in graphs

DOI10.1145/103516.103517MaRDI QIDQ4302836zbMATH OpenOpenAlexFDO

Authors Esther M. Arkin, Mihalis Yannakakis, Christos Papadimitriou

Publication date 13 November 1994

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

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

zbMATH Keywords

bipartite graphcyclesgraphslinear-time algorithmsmodularitypaths

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• LATIN 2004: Theoretical Informatics
• scientific article; zbMATH DE number 617590
• Cycle lengths and minimum degree of graphs
• On path lengths modulo three
• Cycle lengths modulo \(k\) in large 3-connected cubic graphs

Cited in

(22)

• Cycles of length 0 modulo 4 in graphs
• Computing matrix period in max--min algebra
• Strong orientations without even directed circuits
• On the powers of matrices in bottleneck/fuzzy algebra
• Cycles having the same modularity and removable edges in 2-connected graphs
• A trichotomy for regular simple path queries on graphs
• Quick but odd growth of cacti
• Finding induced paths of given parity in claw-free graphs
• Modularity of regular and treelike graphs
• On path lengths modulo three
• Cycles of Prescribed Modularity in Planar Digraphs
• Finding an induced path of given parity in planar graphs in polynomial time
• LATIN 2004: Theoretical Informatics
• A Trichotomy for Regular Trail Queries
• Methods for determining cycles of a specific length in undirected graphs with edge weights
• Shortest odd paths in undirected graphs with conservative weight functions
• Linear independence in bottleneck algebras
• The complexity of computing the period and the exponent of a digraph
• Graph theory. Abstracts from the workshop held January 5--10, 2025
• Cyclic path homology of (di)graphs
• Improved algorithms for perfect graphs and odd holes
• Magic Sets and their application to data integration

This page was built for publication: Modularity of cycles and paths in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4302836)