| Presentation | 2005-01-28 Score Sequence Pair Problems of (r_<11>, r_<12>, r_<22>)-Tournaments : Determination Masaya TAKAHASHI, Takahiro WATANABE, Takeshi YOSHIMURA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | For avoiding the local concentration of a wiring design of a large-scale system LSI and the superfluous load of the circuit of a communication network, the optimization technology using the network technology is indispensable. As the one method of the optimization technology, there is the flow control technique of the network with a directed complete graph structure. The technique can realize an optimal flow under various restrictions by using the score sequence problem of graph theory. In this paper, for some positive integers r_<11>, r_<12> and r_<22>, we propose a score sequence pair of an (r_<11>, r_<12>, r_<22>)-tournament which is a new score sequence problem, and a method determining in O(n) time whether S={S_1, S_2} is a score sequence pair of an (r_<11>, r_<12>, r_<22>)-tournament or not, where S_1=(s_1[1], s_1[2], …, s_1[n_1]) and S_2=(s_2[1], s_2[2], …, s_2[n_2]) are two nonnegative integer sequences and n=n_1+n_2. We think that it is difficult to find a linear time method solving them generally by using the same consideration of known score sequence problems. However we recently obtain that they can be solved in linear time by using the difficult method from the known results. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | (r_<11>, r_<12>, r_<22>)-tournament / score sequence pair / border sequence / basic sequence / turning point / judge point |
| Paper # | COMP2004-72 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2005/1/21(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) | Score Sequence Pair Problems of (r_<11>, r_<12>, r_<22>)-Tournaments : Determination |
| Sub Title (in English) | |
| Keyword(1) | (r_<11>, r_<12>, r_<22>)-tournament |
| Keyword(2) | score sequence pair |
| Keyword(3) | border sequence |
| Keyword(4) | basic sequence |
| Keyword(5) | turning point |
| Keyword(6) | judge point |
| 1st Author's Name | Masaya TAKAHASHI |
| 1st Author's Affiliation | Fukuoka Institute of Technology:Graduate School of Waseda University() |
| 2nd Author's Name | Takahiro WATANABE |
| 2nd Author's Affiliation | Graduate School of Waseda University |
| 3rd Author's Name | Takeshi YOSHIMURA |
| 3rd Author's Affiliation | Graduate School of Waseda University |
| Date | 2005-01-28 |
| Paper # | COMP2004-72 |
| Volume (vol) | vol.104 |
| Number (no) | 642 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |