| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2008-04-18 11:10 Enumeration of Perfect Sequences of Chordal Graph Yasuko Matsui (Tokai Univ.), Ryuhei Uehara (JAIST), Takeaki Uno (NII)  COMP2008-3 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | A graph is chordal if and only if it has no chordless cycle of length more than three. The set of maximal cliques in a chordal graph admits special tree structures called clique trees. A perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. This paper addresses the problem of enumerating all the perfect sequences. Although this problem has statistical applications, no efficient algorithm has been proposed. There are two difficulties with developing this type of algorithm. First, a chordal graph does not generally have a unique clique tree. Second, a perfect sequence can normally be generated by two or more distinct clique trees. Thus it is hard using a straightforward way to generate perfect sequences from each possible clique tree. In this paper, we propose a method to enumerate perfect sequences without constructing clique trees. As a result, we have developed the first polynomial delay algorithm for dealing with this problem. In particular, the time complexity of the algorithm on average is O(1) for each perfect sequence. |
|
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | chordal graph / clique tree / enumeration / perfect sequence / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 108, no. 11, COMP2008-3, pp. 15-22, April 2008. | |
| Paper # | COMP2008-3 | |
| Date of Issue | 2008-04-11 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2008-3 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2008-04-18 - 2008-04-18 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Osaka Prefecture University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2008-04-COMP |
| Language | English |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Enumeration of Perfect Sequences of Chordal Graph |
| Sub Title (in English) | |
| Keyword(1) | chordal graph |
| Keyword(2) | clique tree |
| Keyword(3) | enumeration |
| Keyword(4) | perfect sequence |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Yasuko Matsui |
| 1st Author's Affiliation | Tokai University (Tokai Univ.) |
| 2nd Author's Name | Ryuhei Uehara |
| 2nd Author's Affiliation | Japan Advanced Institute of Science and Technology (JAIST) |
| 3rd Author's Name | Takeaki Uno |
| 3rd Author's Affiliation | National Institute of Informatics (NII) |
| 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 | () |
| Speaker | Author-2 |
| Date Time | 2008-04-18 11:10:00 |
| Presentation Time | 35 minutes |
| Registration for | COMP |
| Paper # | COMP2008-3 |
| Volume (vol) | vol.108 |
| Number (no) | no.11 |
| Page | pp.15-22 |
| #Pages | 8 |
| Date of Issue | 2008-04-11 (COMP) |
[Return to Top Page]