A multi-teacher learning automata computing model for graph partitioning problems

Graph partitioning is an important problem that has extensive applications in many areas, including VLSI design, scientific computing, data mining, geographical information systems, and job scheduling. The graph partitioning problem (GPP) is NP‐complete. There are several heuristic algorithms develo...

Full description

Saved in:
Bibliographic Details
Published in:Electrical engineering in Japan 2004-07, Vol.148 (1), p.46-53
Main Authors: Ikebo, Shigeya, Qian, Fei, Hirata, Hironori
Format: Article
Language:English
Subjects:
graph partitioning problems
learning automata
multi-teacher environments
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph partitioning is an important problem that has extensive applications in many areas, including VLSI design, scientific computing, data mining, geographical information systems, and job scheduling. The graph partitioning problem (GPP) is NP‐complete. There are several heuristic algorithms developed for finding a reasonably good solution. The most famous partitioning methods are simulated annealing (SA) and the mean field algorithm (MFA), both known to produce good partitioning for a wide class of problems, and they are used quite extensively. However, these methods are very expensive in terms of time and very sensitive to parameter tuning methods. In this paper, a new parameter‐free algorithm for GPP has been proposed. The algorithm has been constructed using the S‐model learning automata with multi‐teacher random environments. As shown in our experiments, the proposed algorithm has some advantages over SA, MFA, and ParMeTiS. © 2004 Wiley Periodicals, Inc. Electr Eng Jpn, 148(1): 46–53, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/eej.10310
ISSN:0424-7760
1520-6416
DOI:10.1002/eej.10310