| Presentation | 2004/4/15 An Exact Algorithm for Solving the Maximum Weighted Clique Problem with Using Comparability Supergraphs Kazuaki YAMAGUCHI, Yoshie SAKAKIBARA, Sumio MASUDA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We show a method for calculating the upper bound of the weight of the maximum weighted clique problem with using comparability supergraphs. With our method, many algorithms for the maximum cadinality clique problem with using the branch-and-bound technique based on coloring are naturally extended to algorithms for the maximum weighted clique problem. Our method uses the maximum weighted clique in a comparability supergraph of the given graph at the bounding stage. We investigate the efficiency and the problems of our method some with some computational experiments. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | branch-and-bound / vertex coloring / comparabilitv graph / transitive orientation |
| Paper # | COMP2004-4 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2004/4/15(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) | An Exact Algorithm for Solving the Maximum Weighted Clique Problem with Using Comparability Supergraphs |
| Sub Title (in English) | |
| Keyword(1) | branch-and-bound |
| Keyword(2) | vertex coloring |
| Keyword(3) | comparabilitv graph |
| Keyword(4) | transitive orientation |
| 1st Author's Name | Kazuaki YAMAGUCHI |
| 1st Author's Affiliation | Faculty of Engineering, Kobe University() |
| 2nd Author's Name | Yoshie SAKAKIBARA |
| 2nd Author's Affiliation | Kobe University Graduate School of Science and Technology |
| 3rd Author's Name | Sumio MASUDA |
| 3rd Author's Affiliation | Faculty of Engineering, Kobe University |
| Date | 2004/4/15 |
| Paper # | COMP2004-4 |
| Volume (vol) | vol.104 |
| Number (no) | 16 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |