Complete-subgraph-transversal-sets problem on bounded treewidth graphs (Q2045031)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Complete-subgraph-transversal-sets problem on bounded treewidth graphs |
scientific article |
Statements
Complete-subgraph-transversal-sets problem on bounded treewidth graphs (English)
0 references
11 August 2021
0 references
The paper considers the Complete-Subgraph-Transversal-Set problem and the \(L\)-Max Complete-Subgraph-Transversal-Set problem. Polynomial time algorithms are presented for the two problems on graphs of bounded treewidth. The authors show the connections between these two problems with some other known NP-complete problems such as the Clique-Transversal-Set problem on graphs and the Vertex-Cover problem on hypergraphs.
0 references
treewidth
0 references
complete subgraph
0 references
NP-complete problems
0 references
algorithms
0 references
0 references
