Quick but odd growth of cacti

DOI10.1007/S00453-017-0317-1MaRDI QIDQ2408205zbMATH OpenOpenAlexFDO

Authors Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh

Publication date 10 October 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2015/5588/

zbMATH Keywords

diamond hitting seteven cycle transversalfixed parameter tractabilityrandomized algorithms

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 6784975
• An improved deterministic parameterized algorithm for cactus vertex deletion
• Parameterized algorithms for even cycle transversal
• Hitting selected (odd) cycles
• A faster parameterized algorithm for pseudoforest deletion

Cites work

• (Meta) Kernelization
• A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
• Fundamentals of parameterized complexity
• Graph theory
• Hitting diamonds and growing cacti
• Hitting forbidden minors: approximation and kernelization
• scientific article; zbMATH DE number 1467487 (Why is no real title available?)
• Interval deletion is fixed-parameter tractable
• Modularity of cycles and paths in graphs
• On the presence of disjoint subgraphs of a specified type
• Parameterized algorithms
• Parameterized algorithms for even cycle transversal
• Subexponential parameterized algorithm for minimum fill-in
• The even-path problem for graphs and digraphs
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(7)

• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
• Faster deterministic algorithm for cactus vertex deletion
• An improved deterministic parameterized algorithm for cactus vertex deletion
• Odd multiway cut in directed acyclic graphs
• Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
• scientific article; zbMATH DE number 6784975 (Why is no real title available?)
• Faster parameterized algorithm for r-pseudoforest deletion

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Quick but odd growth of cacti

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