The complexity of determining a shortest cycle of even length
From MaRDI portal
Publication:1052821
DOI10.1007/BF02251238zbMath0516.68041OpenAlexW146202307MaRDI QIDQ1052821
Publication date: 1983
Published in: Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02251238
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (13)
The cycle's structure of embedded graphs in surfaces ⋮ Computing clique and chromatic number of circular-perfect graphs in polynomial time ⋮ On the negative cost girth problem in planar networks ⋮ Determination of a circuit in a directed graph ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ How many attackers can selfish defenders catch? ⋮ Finding even cycles even faster ⋮ Finding a shortest cycle in a subspace of the cycle space of a graph ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Finding shorter cycles in a weighted graph ⋮ Triangle-free strongly circular-perfect graphs ⋮ On fractional cut covers ⋮ Ramsey numbers and an approximation algorithm for the vertex cover problem
Cites Work
This page was built for publication: The complexity of determining a shortest cycle of even length