Finding Even Cycles Even Faster

DOI10.1137/S0895480194274133MaRDI QIDQ4337730zbMATH OpenOpenAlexFDO

Authors Raphael Yuster, Uri Zwick

Publication date 26 May 1997

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480194274133

zbMATH Keywords

graph algorithmscycles

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• Finding even cycles even faster
• scientific article; zbMATH DE number 3876619
• scientific article; zbMATH DE number 3937199
• Finding even cycles faster via capped k-walks
• Efficient approximation algorithms for shortest cycles in undirected graphs

Cited in

(29)

• Finding and counting small tournaments in large tournaments
• An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Finding even cycles faster via capped k-walks
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Equitable total-coloring of subcubic graphs
• Answering conjunctive queries with inequalities
• scientific article; zbMATH DE number 3876619 (Why is no real title available?)
• Removing additive structure in 3SUM-based reductions
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• scientific article; zbMATH DE number 7765381 (Why is no real title available?)
• Two-dimensional pattern matching against local and regular-like picture languages
• Finding shorter cycles in a weighted graph
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Detecting directed 4-cycles still faster
• Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs
• Finding a shortest cycle in a subspace of the cycle space of a graph
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• How many attackers can selfish defenders catch?
• Map graphs having witnesses of large girth
• A shortest cycle for each vertex of a graph
• Counting Homomorphic Cycles in Degenerate Graphs
• scientific article; zbMATH DE number 7559367 (Why is no real title available?)
• Computational complexity aspects of super domination
• scientific article; zbMATH DE number 3937199 (Why is no real title available?)
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Finding and counting given length cycles
• On the negative cost girth problem in planar networks

This page was built for publication: Finding Even Cycles Even Faster

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