Detecting directed 4-cycles still faster

DOI10.1016/S0020-0190(03)00252-7MaRDI QIDQ1014385zbMATH OpenOpenAlexFDO

Authors Friedrich Eisenbrand, Fabrizio Grandoni

Publication date 28 April 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(03)00252-7

zbMATH Keywords

algorithmscomputational complexitydirected 4-cycle

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Recommendations

• Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
• Finding and counting given length cycles
• Finding four-node subgraphs in triangle time
• scientific article; zbMATH DE number 6469131
• scientific article; zbMATH DE number 3937199

Cites work

• Color-coding
• Fast rectangular matrix multiplication and applications
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Finding and counting small induced subgraphs efficiently
• Finding Even Cycles Even Faster
• Matrix multiplication via arithmetic progressions

Cited in

(4)

• A faster test for 4-flow-criticality in snarks
• Finding four-node subgraphs in triangle time
• Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
• Counting Homomorphic Cycles in Degenerate Graphs

This page was built for publication: Detecting directed 4-cycles still faster

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