| Presentation | 1997/11/14 Parallel Complexity of the Lexicographically First Maximal Subgraph Problems on Restricted Graphs Ryuhei Uehara, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Longest directed path length (LDPL) is defined by the length of the longest path of the directed acyclic graph of a given undirected graph. The LDPL of a graph measures the parallelization for the lexicographically first maximal subgraph (LFMS) problems. That is, the parallel complexity of the problems gradually increases as the value measured on a graph grows; the LFMS problems are in NC on graphs of LDPL O(log^k n), and P-complete on graphs of LDPL cn^ε. It is worth remarking that the problem to compute the LDPL is in NC^2. The LDPL on a random graph is also considered, and the threshold value for the LDPL l is 1/n for a random graph G(n,p). |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Analysis of algorithms / NC algorithms / P-completeness / random graphs / the lexicographically first maximal independent set problem / the lexicographically first maximal subgraph problems. |
| Paper # | COMP97-68 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1997/11/14(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Parallel Complexity of the Lexicographically First Maximal Subgraph Problems on Restricted Graphs |
| Sub Title (in English) | |
| Keyword(1) | Analysis of algorithms |
| Keyword(2) | NC algorithms |
| Keyword(3) | P-completeness |
| Keyword(4) | random graphs |
| Keyword(5) | the lexicographically first maximal independent set problem |
| Keyword(6) | the lexicographically first maximal subgraph problems. |
| 1st Author's Name | Ryuhei Uehara |
| 1st Author's Affiliation | Center for Information Science, Tokyo Woman's Christian University() |
| Date | 1997/11/14 |
| Paper # | COMP97-68 |
| Volume (vol) | vol.97 |
| Number (no) | 375 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |