A Genetic Algorithm for Finding the Pagenumber of Interconnection Networks

✍ Scribed by Nidhi Kapoor; Mark Russell; Ivan Stojmenovic; Albert Y. Zomaya

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 151 KB
• Volume: 62
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2001.1789

✦ Synopsis

A ''book-embedding'' of a graph G comprises embedding the graph's nodes along the spine of a book and embedding the edges on the pages so that the edges embedded on the same page do not intersect. This is also referred to as the page model. The ''pagenumber'' of a graph is the thickness of the smallest (in number of pages) book into which G can be embedded. The problem has been studied only for some specific kind of graphs. The pagenumber problem is known to be NP-complete, even if the order of nodes on the spine is fixed. Using genetic algorithms, we describe the first algorithm for solving the pagenumber problem that can be applied on arbitrary graphs. Experimental results for several kinds of graphs are obtained. We were particularly interested in graphs that correspond to some well-known interconnection networks (such as hypercubes and meshes). We also introduced and experimented with 2-D pagenumber model for embedding graphs.