Presentation | 2015-03-03 Methods of Generating Regular Graphs with Short Average Path Length Keisuke FUJITA, Norikazu TAKAHASHI, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | The problem of finding a regular graph with given number of vertices and given degree that minimizes the average path length is studied. For example, if all terminals in a multi-hop wireless network have the same number of communication channels, the transmission rate in the network depends strongly on the average path length of the regular graph representing the connections between terminals. An important theoretical result related to this problem is the lower bound for the average path length derived by Cerf et al. In this report, we propose some methods of generating automatically regular graphs with short average path length, and examine their effectiveness numerically. It is shown that the lower bound of Cerf et al. is achieved by the proposed methods for some cases. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | regular graph / average path length / minimization / algorithm |
Paper # | NLP2014-144 |
Date of Issue |
Conference Information | |
Committee | NLP |
---|---|
Conference Date | 2015/2/24(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 | Nonlinear Problems (NLP) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Methods of Generating Regular Graphs with Short Average Path Length |
Sub Title (in English) | |
Keyword(1) | regular graph |
Keyword(2) | average path length |
Keyword(3) | minimization |
Keyword(4) | algorithm |
1st Author's Name | Keisuke FUJITA |
1st Author's Affiliation | Faculty of Engineering, Okayama University() |
2nd Author's Name | Norikazu TAKAHASHI |
2nd Author's Affiliation | Graduate School of Natural Science and Technology, Okayama University |
Date | 2015-03-03 |
Paper # | NLP2014-144 |
Volume (vol) | vol.114 |
Number (no) | 484 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |