Back to Search
Start Over
Fast exact algorithms for some connectivity problems parametrized by clique-width
- Publication Year :
- 2017
-
Abstract
- Given a clique-width $k$-expression of a graph $G$, we provide $2^{O(k)}\cdot n$ time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted Steiner Tree, Connected Dominating Set, or Connected Vertex Cover. We also propose a $2^{O(k)}\cdot n$ time algorithm for Feedback Vertex Set. The best running times for all the considered cases were either $2^{O(k\cdot \log(k))}\cdot n^{O(1)}$ or worse.
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1707.03584
- Document Type :
- Working Paper