Let F be a family of finite simple graphs, such as planar graphs, Cayley graphs, 4-colorable graphs, etc. The basic question is whether there exists a polynomial-time algorithm to decide whether a given graph G belongs to F. Do you know any summary (for example in the form of table) with state-of-the-art for this problem: for which families F thre there is a polynomial algorithm (and what is the fastest known algorithm), for which families the problem is NP complete, and for which families it is open.
|
2 | fixed a couple of typos | ||
Recognision Recognition of graph families. |
||||
|
|
1 |
|
||
Recognision of graph families.Let F be a family of finite simple graphs, such as planar graphs, Cayley graphs, 4-colorable graphs, etc. The basic question is whether there exists a polynomial-time algorithm to decide whether a given graph G belongs to F. Do you know any summary (for example in the form of table) with state-of-the-art for this problem: for which families F thre is a polynomial algorithm (and what is the fastest known algorithm), for which families the problem is NP complete, and for which families it is open.
|
||||
