Packing Directed Circuits through Prescribed Vertices Bounded Fractionally

DOI10.1137/100786423zbMath1256.05190OpenAlexW1993149037MaRDI QIDQ4899052

Naonori Kakimura, Ken-ichi Kawarabayashi

Publication date: 4 January 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b4ca5fe12a89b264642718ac5ce82da3772a2dd5

zbMATH Keywords

feedback vertex setsdisjoint circuitsFPT approximability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

Frames, $A$-Paths, and the Erdös--Pósa Property ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ Erdős-Pósa property of chordless cycles and its applications ⋮ Disjoint cycles intersecting a set of vertices ⋮ Graphs without two vertex-disjoint \(S\)-cycles ⋮ $K_4$-Subdivisions Have the Edge-Erdös--Pósa Property

This page was built for publication: Packing Directed Circuits through Prescribed Vertices Bounded Fractionally