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

cyclesgraph algorithms

Mathematics Subject Classification ID

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

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

(35)

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

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)