Creator |
|
Language |
|
Publisher |
|
|
Date |
|
Source Title |
|
Vol |
|
Publication Type |
|
Access Rights |
|
Related DOI |
|
|
Related URI |
|
|
Relation |
|
|
Abstract |
This is a survey on complexity issues of subgraph problems proved in a systematic way. We deal with vertex-deletion and edge-deletion problems which can be viewed as subgraph problems. General NP-comp...leteness theorems are presernted for these problems. We also present a systematized result which shoaws polynomial time algorithms for these problems restricted to series-parallel graphs. Another problem we consider in this paper is the lelxicographically first maximal subgraph problems which appear in connection with parallel complexity theory.show more
|