<technical report>
Bounded Degree Maximal Subgraph Problems are in NC
Creator | |
---|---|
Language | |
Publisher | |
Date | |
Source Title | |
Vol | |
Publication Type | |
Access Rights | |
Related DOI | |
Related URI | |
Relation | |
Abstract | We show that the problem of finding a maximal vertex-induced (resp., edge-induced) subgraph of maximum degree k is in $ NC^2 $ for $ k leq 0 (resp., k leq 1) $. For these problems, we develope a meth...od which exploits the NC algorithm for the maximal independent set problem.show more |
Hide fulltext details.
File | FileType | Size | Views | Description |
---|---|---|---|---|
rifis-tr-27 | 930 KB | 417 |
Details
Record ID | |
---|---|
Peer-Reviewed | |
Notes | |
Type | |
Created Date | 2009.04.22 |
Modified Date | 2017.01.20 |