The complexity of determining a shortest cycle of even length

DOI10.1007/BF02251238zbMath0516.68041OpenAlexW146202307MaRDI QIDQ1052821

Burkhard Monien

Publication date: 1983

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02251238

zbMATH Keywords

shortest cycleefficient algorithms

Mathematics Subject Classification ID

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

• Weakly bipartite graphs and the max-cut problem
• Finding a Minimum Circuit in a Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of determining a shortest cycle of even length