Detecting directed 4-cycles still faster

DOI10.1016/S0020-0190(03)00252-7zbMATH Open1175.68187OpenAlexW2069463493MaRDI QIDQ1014385FDOQ1014385

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

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

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)

Cites Work

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

Cited In (4)

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

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)