(Back to Session Schedule)

The 23rd International Technical Conference on Circuits/Systems, Computers and Communications

Session F3  Graph, Petri Nets & Algorithms 3
Time: 15:30 - 16:42 Monday, July 7, 2008
Location: 8F 803 Room
Chairs: Toshiya Mashima (Hiroshima International University, Japan), Apirat Siritaratiwat (Khon Kaen University, Thailand)

F3-1 (Time: 15:30 - 15:48)
TitleA New Exact Algorithm for the Maximum Weight Clique Problem
Author*Kazuaki Yamaguchi, Sumio Masuda (Kobe University, Japan)
Pagepp. 317 - 320
Keywordclique, maximum weight clique, branch-and-bound, upper bound, longest path
AbstractGiven an undirected graph with weight for each vertex, the maximum weight clique problem is to find the clique of the maximum weight. Ostergard proposed a fast exact algorithm for solving this problem. We show his algorithm is not efficient for very dense graphs. We propose an exact algorithm for the problem, which is faster than Ostergard's algorithm in case the graph is dense. We show the efficiency of our algorithm with some experimental results.

F3-2 (Time: 15:48 - 16:06)
TitleA Sufficient Condition for Diagnosability of Large-Scale Discrete Event Systems
Author*Shigemasa Takai (Kyoto Institute of Technology, Japan)
Pagepp. 321 - 324
Keyworddiscrete event system, failure diagnosis, diagnosability
AbstractWe study the diagnosability property of a large-scale discrete event system that is modeled by the synchronous composition of n subsystems. In order to verify the necessary and sufficient condition for the diagnosability property, we have to perform operations over the entire system model, which suffers from the state space explosion problem. Motivated by this, we present a sufficient condition for the diagnosability property that can be tested by using only the subsystem models.

F3-3 (Time: 16:06 - 16:24)
TitleEfficient Floorplanning by O-Tree with Genetic Algorithm
Author*Tetsutarou Hara, Katsumi Harashima (Osaka Institute of Technology, Japan)
Pagepp. 325 - 328
KeywordFloorplanning, O-Tree, GA
AbstractModule placement is an important phase for VLSI layout design. However, huge time is necessary to obtain the optimal layout. This paper proposes a block packing method using O-Tree with Genetic Algorithm. O-Tree can transform a code into a placement in linear time to the number of modules. Moreover, Genetic Algorithm is effective for searching a good layout because it can search two or more layouts concurrently. In experiment, we have confirmed to obtain nearly optimal packing results efficiently.

F3-4 (Time: 16:24 - 16:42)
TitleA Parts Arrangement Algorithm for Note PC - An Algorithm for 3D Bin Packing Problem with Arrangement Constraints -
Author*Shigeta Kuninobu, Keiichi Handa, Yasushi Sasaki, Takashi Iikubo (Toshiba Corporation, Japan)
Pagepp. 329 - 332
KeywordParts Arrangement, Heuristics, 3D Bin Packing, Note PC, Arrangement Constraints
AbstractWe propose a parts arrangement algorithm for equipment such as note PCs. In parts arrangements for actual equipment, a large part of the parts have the arrangement constraints and requirements. The proposed algorithm minimizes the equipment thickness keeping the given equipment depth and width. The algorithm outputs multiple thin arrangement results which satisfy the arrangement constraints and requirements. We evaluated the proposed method by comparing with the results attained by the skilled factory designers.