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

graphspathsmodularitybipartite graphcycleslinear-time algorithms

Mathematics Subject Classification ID

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

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

(18)

• Quick but odd growth of cacti
• Linear independence in bottleneck algebras
• Cycles having the same modularity and removable edges in 2-connected graphs
• Magic Sets and their application to data integration
• A trichotomy for regular simple path queries on graphs
• Modularity of regular and treelike graphs
• Computing matrix period in max--min algebra
• A Trichotomy for Regular Trail Queries
• Shortest odd paths in undirected graphs with conservative weight functions
• Methods for determining cycles of a specific length in undirected graphs with edge weights
• Finding an induced path of given parity in planar graphs in polynomial time
• LATIN 2004: Theoretical Informatics
• Cycles of Prescribed Modularity in Planar Digraphs
• Cycles of length 0 modulo 4 in graphs
• On path lengths modulo three
• On the powers of matrices in bottleneck/fuzzy algebra
• Strong orientations without even directed circuits
• Finding induced paths of given parity in claw-free graphs

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)