An Improved Algorithm for Finding Cycles Through Elements

DOI10.1007/978-3-540-68891-4_26MaRDI QIDQ3503860zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
• A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
• Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
• Odd cycle packing
• Color-coding

Cites work

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

Cited in

(13)

• Detecting cycles through three fixed vertices in a graph
• Subexponential algorithms for partial cover problems
• A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
• Half-integral linkages in highly connected directed graphs
• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• Walking through waypoints
• Cyclability, connectivity and circumference
• Parameterized algorithms for list \(K\)-cycle
• Computing paths of large rank in planar frameworks deterministically
• On the complexity of the bilevel shortest path problem
• Determinantal sieving
• Computing paths of large rank in planar frameworks deterministically
• Fixed-parameter tractability of maximum colored path and beyond

This page was built for publication: An Improved Algorithm for Finding Cycles Through Elements

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