| Paper Abstract and Keywords |
| Presentation |
2006-04-26 16:20
An exact algorithm for the label placement problem
Yuichi Inoue, Kazuaki Yamaguchi, Sumio Masuda (Kobe Univ.) |
| Abstract |
(in Japanese) |
(See Japanese page) |
| (in English) |
Given sites on a map and their labels with specified size, the label placement problem is to find an appropriate placement for each label. We consider the label placement problem in which the candidates for the position of each label are given. In this case the problem can be represented as the maximum independent set problem. In this paper, we propose a fast algorithm for finding a maximum independent set in a graph which is produced from the label placement problem. We show by some computer experiments that our algorithm is more efficient than the well-known algorithm. |
| Keyword |
(in Japanese) |
(See Japanese page) |
| (in English) |
label placement problem / graph / independent set / clique / branch-and-bound algorithm / separator / / |
| Reference Info. |
IEICE Tech. Rep., vol. 106, no. 29, COMP2006-9, pp. 63-67, April 2006. |
| Paper # |
COMP2006-9 |
| Date of Issue |
2006-04-19 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| Download PDF |
|
| Conference Information |
| Committee |
COMP |
| Conference Date |
2006-04-26 - 2006-04-26 |
| Place (in Japanese) |
(See Japanese page) |
| Place (in English) |
Kyoto University |
| Topics (in Japanese) |
(See Japanese page) |
| Topics (in English) |
|
| Paper Information |
| Registration To |
COMP |
| Conference Code |
2006-04-COMP |
| Language |
Japanese |
| Title (in Japanese) |
(See Japanese page) |
| Sub Title (in Japanese) |
(See Japanese page) |
| Title (in English) |
An exact algorithm for the label placement problem |
| Sub Title (in English) |
|
| Keyword(1) |
label placement problem |
| Keyword(2) |
graph |
| Keyword(3) |
independent set |
| Keyword(4) |
clique |
| Keyword(5) |
branch-and-bound algorithm |
| Keyword(6) |
separator |
| Keyword(7) |
|
| Keyword(8) |
|
| 1st Author's Name |
Yuichi Inoue |
| 1st Author's Affiliation |
Kobe University (Kobe Univ.) |
| 2nd Author's Name |
Kazuaki Yamaguchi |
| 2nd Author's Affiliation |
Kobe University (Kobe Univ.) |
| 3rd Author's Name |
Sumio Masuda |
| 3rd Author's Affiliation |
Kobe University (Kobe Univ.) |
| 4th Author's Name |
|
| 4th Author's Affiliation |
() |
| 5th Author's Name |
|
| 5th Author's Affiliation |
() |
| 6th Author's Name |
|
| 6th Author's Affiliation |
() |
| 7th Author's Name |
|
| 7th Author's Affiliation |
() |
| 8th Author's Name |
|
| 8th Author's Affiliation |
() |
| 9th Author's Name |
|
| 9th Author's Affiliation |
() |
| 10th Author's Name |
|
| 10th Author's Affiliation |
() |
| 11th Author's Name |
|
| 11th Author's Affiliation |
() |
| 12th Author's Name |
|
| 12th Author's Affiliation |
() |
| 13th Author's Name |
|
| 13th Author's Affiliation |
() |
| 14th Author's Name |
|
| 14th Author's Affiliation |
() |
| 15th Author's Name |
|
| 15th Author's Affiliation |
() |
| 16th Author's Name |
|
| 16th Author's Affiliation |
() |
| 17th Author's Name |
|
| 17th Author's Affiliation |
() |
| 18th Author's Name |
|
| 18th Author's Affiliation |
() |
| 19th Author's Name |
|
| 19th Author's Affiliation |
() |
| 20th Author's Name |
|
| 20th Author's Affiliation |
() |
| Speaker |
Author-1 |
| Date Time |
2006-04-26 16:20:00 |
| Presentation Time |
35 minutes |
| Registration for |
COMP |
| Paper # |
COMP2006-9 |
| Volume (vol) |
vol.106 |
| Number (no) |
no.29 |
| Page |
pp.63-67 |
| #Pages |
5 |
| Date of Issue |
2006-04-19 (COMP) |