Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity.
Nina ChiarelliTatiana Romina HartingerMatthew JohnsonMartin MilanicDaniël PaulusmaPublished in: Theor. Comput. Sci. (2018)
Keyphrases
- tractable cases
- bounded treewidth
- np complete
- connected components
- spanning tree
- causal models
- computational complexity
- undirected graph
- directed graph
- connected graphs
- phase transition
- graph theory
- worst case
- graph theoretic
- np hardness
- np hard
- relational databases
- decision problems
- weighted graph
- random walk
- data management
- polynomial size
- bayesian networks