| Presentation | 2000/11/2 NP-completeness of a minimax realization problem on undirected flow networks Hiroshi TAMURA, Masakazu SENGOKU, Shoji SHINODA, Takeo ABE, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We consider a realization problem of an undirected flow network N from a matrix M. We assume that M is not always a terminal capacity matrix. In this condition, we considered problems to minimize differences between capacities between vertex pairs in N, and elements of M in previous papers. In this paper, we generalize the concept of difference and we show that a part of a problem related minimax realization problems is NP-complete. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graph theory / flow network / terminal capacity matrix / realization problem / NP-complete |
| Paper # | CAS 2000-63,CST 2000-18 |
| Date of Issue |
| Conference Information | |
| Committee | CST |
|---|---|
| Conference Date | 2000/11/2(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 | Concurrent System Technology (CST) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | NP-completeness of a minimax realization problem on undirected flow networks |
| Sub Title (in English) | |
| Keyword(1) | graph theory |
| Keyword(2) | flow network |
| Keyword(3) | terminal capacity matrix |
| Keyword(4) | realization problem |
| Keyword(5) | NP-complete |
| 1st Author's Name | Hiroshi TAMURA |
| 1st Author's Affiliation | Dept. of Information and Electronics Engineering, Niigata Institute of Technology() |
| 2nd Author's Name | Masakazu SENGOKU |
| 2nd Author's Affiliation | Faculty of Engineering, Niigata University |
| 3rd Author's Name | Shoji SHINODA |
| 3rd Author's Affiliation | Faculty of Science and Engineering, Chuo University |
| 4th Author's Name | Takeo ABE |
| 4th Author's Affiliation | Dept. of Information and Electronics Engineering, Niigata Institute of Technology |
| Date | 2000/11/2 |
| Paper # | CAS 2000-63,CST 2000-18 |
| Volume (vol) | vol.100 |
| Number (no) | 417 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |