An Improved Algorithm for Finding Cycles Through Elements

DOI10.1007/978-3-540-68891-4_26zbMath1143.68503OpenAlexW1558321388MaRDI QIDQ3503860

Ken-ichi Kawarabayashi

Publication date: 10 June 2008

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-68891-4_26

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Cyclability, connectivity and circumference, Subexponential algorithms for partial cover problems, Parameterized algorithms for list \(K\)-cycle, Half-integral linkages in highly connected directed graphs, Walking through waypoints, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Any four independent edges of a 4-connected graph are contained in a circuit
• Graph minors. V. Excluding a planar graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On circuits through five edges
• The subgraph homeomorphism problem
• A nine point theorem for 3-connected graphs
• Circuits through specified edges
• Cycles through specified vertices of a graph
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Circuits containing specified edges
• Note on circuits containing specified edges
• Highly connected sets and the excluded grid theorem
• Quickly excluding a planar graph
• Rooted routing in the plane
• Graph minors. XVI: Excluding a non-planar graph
• Cycles through a prescribed vertex set in \(n\)-connected graphs.
• One or two disjoint circuits cover independent edges. Lovász-Woodall conjecture
• Graph minors. XIII: The disjoint paths problem
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Finding paths and cycles of superpolylogarithmic length
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The NP-completeness column: An ongoing guide