Improves exact algorithm for minimum edge deletion to connected cactus from O*(3^n) to O*(2^n), with O*(2^n n^{O(q)}) for q distinct nonnegative costs and O*(2^n (W+1)) pseudo-polynomial for integer costs summing to W.
Edge deletion to tree-like graph classes.Discrete Applied Mathematics, 348:122–131, 2024
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Exact Algorithms for Edge Deletion to Cactus Graphs and Weighted Variants
Improves exact algorithm for minimum edge deletion to connected cactus from O*(3^n) to O*(2^n), with O*(2^n n^{O(q)}) for q distinct nonnegative costs and O*(2^n (W+1)) pseudo-polynomial for integer costs summing to W.