ON DISJOINT CYCLES

DOI10.1142/S0129054194000049zbMath0803.05030MaRDI QIDQ4304619

Hans L. Bodlaender

Publication date: 2 January 1995

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054194000049

zbMATH Keywords

treewidth; linear time algorithm; feedback vertex set; tree-decomposition; disjoint cycles

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

68W10: Parallel algorithms in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, On the Complexity of Singly Connected Vertex Deletion, Parameterized Complexity of Fair Feedback Vertex Set Problem, Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs, Packing Arc-Disjoint Cycles in Tournaments, Packing Cycles Faster Than Erdos--Posa, Parameterized Graph Cleaning Problems, Inapproximability of $H$-Transversal/Packing, An improved FPT algorithm for independent feedback vertex set, The parameterized complexity of cycle packing: indifference is not an issue, Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs, A parameterized algorithm for subset feedback vertex set in tournaments, On group feedback vertex set parameterized by the size of the cutset, Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems, Vertex-disjoint directed and undirected cycles in general digraphs, On feedback vertex set: new measure and new structures, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Parameterized complexity of finding connected induced subgraphs, Improved algorithms for feedback vertex set problems, Parameterized graph cleaning problems, A cubic kernel for feedback vertex set and loop cutset, Satisfactory graph partition, variants, and generalizations, Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3, A partial k-arboretum of graphs with bounded treewidth, On interval routing schemes and treewidth, The decycling number of outerplanar graphs, Faster deterministic \textsc{Feedback Vertex Set}, Improved analysis of highest-degree branching for feedback vertex set, On the complexity of singly connected vertex deletion, Mim-width. II. The feedback vertex set problem, Obtaining a planar graph by vertex deletion, Contracting graphs to paths and trees, An improved parameterized algorithm for the independent feedback vertex set problem, The satisfactory partition problem, Parameterized complexity of fair feedback vertex set problem, Packing arc-disjoint cycles in tournaments, Arc-Disjoint Directed and Undirected Cycles in Digraphs, Backdoors to Satisfaction, What’s Next? Future Directions in Parameterized Complexity, Subset Feedback Vertex Set Is Fixed-Parameter Tractable, A Quartic Kernel for Pathwidth-One Vertex Deletion, Unnamed Item, A Linear Kernel for Planar Feedback Vertex Set, Iterative Compression for Exactly Solving NP-Hard Minimization Problems