Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey (Q1062758)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey |
scientific article |
Statements
Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey (English)
0 references
1985
0 references
The paper is concerned with polynomial-time algorithms for restricted versions of some NP-hard problems on graphs. It surveys the use of table- based reduction methods for solving combinatorial problems defined on graphs and hypergraphs of bounded dimension and for problems defined on clique separable graphs and complement decomposable graphs. Some examples illustrate the use of the methods described.
0 references
polynomial-time algorithms
0 references
NP-hard problems on graphs
0 references
table-based reduction methods
0 references
