The degree-constrained minimum spanning tree (DCMST) problem is the problem of finding the minimum cost spanning tree in an edge weighted complete graph such that each vertex in the spanning tree has degree ≤dfor somed≥ 2. The DCMST problem is known to be NP-hard. This paper presents an ant-based algorithm to find low cost degree-constrained spanning trees (DCST). The algorithm employs a set of ants which traverse the graph and identify a set of candidate edges, from which a DCST is constructed. Local optimization algorithms are then used to further improve the DCST. Extensive experiments using 612 problem instances show many improvements over existing algorithms.

This paper describes a general scheme to convert sequential ant-based algorithms into parallel shared memory algorithms. The scheme is applied to an ant-based algorithm for the maximum clique problem. Extensive experimental results indicate that the parallel version provides noticeable improvements to the running time while maintaining comparable solution quality to that of the sequential version.

This paper presents an algorithm for solving a number of generalized graph coloring problems. Specifically, it gives an agent-based algorithm for the Bandwidth Coloring problem. Using a standard method for preprocessing the input, the same algorithm can also be used to solve the Multicoloring and Bandwidth Multicoloring problems. In the algorithm a number of agents, called ants, each of which colors a portion of the graph, collaborate to obtain a coloring of the entire graph. This coloring is then further improved by a local optimization algorithm. Experimental results on a set of benchmark graphs for these generalized coloring problems show that this algorithm performs very well compared to other heuristic approaches.

A spanning tree of a graph such that each vertex in the tree has degree at most d is called a degree-constrained spanning tree. The problem of finding the degree-constrained spanning tree of minimum cost in an edge weighted graphis well known to be NP-hard. In this paper we give an Ant-Based algorithm for finding low cost degree-constrained spanning trees. Ants are used to identify a set of candidate edges from which a degree-constrained spanning tree can be constructed. Extensive experimental results show that the algorithm performs very well against other algorithms on a set of 572 problem instances.

This paper presents an ant-based approach for solving the Traveling Salesman Problem (TSP). Novel concepts of this algorithm that distinguish it from the other heuristics are the inclusion of a preprocessing stage and the use of a modified version of an ant-based approach with local optimization in multi stages. Experimental results show that this algorithm outperforms ACS [1] and is comparable to MMAS [4] for Euclidean TSP instances. Of the 40 instances of Euclidean TSP from TSPLIB [5] that were tested, this algorithm found the optimal solution for 37 instances. For the remaining instances, this algorithm returned solutions that were within 0.3% of the optimum.

Given the amino acid sequence of a protein, predicting its tertiary structure is known as the protein folding problem. This problem has been widely studied under the HP model in which each amino acid is classified, based on its hydrophobicity, as an H (hydrophobic or non-polar) or a P (hydrophilic or polar). Conformation of a protein in the HP model is embedded as a self-avoiding walk in either a two-dimensional or a three-dimensional lattice. The protein folding problem in the HP model is to find a lowest energy conformation. This problem is known to be NP-hard in both two-dimensional and three-dimensional square lattices. In this paper, we present an efficient genetic algorithm for the protein folding problem under the HP model in the two-dimensional square lattice. A special feature of this algorithm is its usage of secondary structures, that the algorithm evolves, as building blocks for the conformation. Experimental results on benchmark sequences show that the algorithm performs very well against existing evolutionary algorithms and Monte Carlo algorithms.

A genetic algorithm for partitioning a hypergraph into two disjoint graphs of minimum ratio cut is presented. As the Fiduccia-Mattheyses graph partitioning heuristic turns out to be not effective when used in the context of a hybrid genetic algorithm, we propose a modification of the Fiduccia-Mattheyses heuristic for more effective and faster space search by introducing a number of novel features. We also provide a preprocessing heuristic for genetic encoding designed solely for hypergraphs which helps genetic algorithms exploit clustering information of input graphs. Supporting combinatorial arguments for the new preprocessing heuristic are also provided. Experimental results on industrial benchmarks circuits showed visible improvement over recently published algorithms with a lower growth rate of running time.

Hybrid genetic algorithms (GAs) for the graph partitioning problem are described. The algorithms include a fast local improvement heuristic. One of the novel features of these algorithms is the schema preprocessing phase that improves GAs' space searching capability, which in turn improves the performance of GAs. Experimental tests on graph problems with published solutions showed that the new genetic algorithms performed comparable to or better than the multistart Kernighan-Lin algorithm and the simulated annealing algorithm. Analyses of some special classes of graphs are also provided showing the usefulness of schema preprocessing and supporting the experimental results.

Article A fast and stable hybrid genetic algorithm for the ratio-cut partitioning problem on hypergraphs Share on Authors: Thang Nguyen Bui Dept. of Computer Science, Pennsylvania State University, Middletown, PA Dept. of Computer Science, Pennsylvania State University, Middletown, PAView Profile , Byung Ro Moon Dept. of Computer Science and Engineering, Pennsylvania State University, University Park, PA Dept. of Computer Science and Engineering, Pennsylvania State University, University Park, PAView Profile Authors Info & Claims DAC '94: Proceedings of the 31st annual Design Automation ConferenceJune 1994 Pages 664–669https://doi.org/10.1145/196244.196607Published:06 June 1994 20citation407DownloadsMetricsTotal Citations20Total Downloads407Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A common problem in graph theory is that of dividing the vertices of a graph into two sets of prescribed size while cutting a minimum number of edges. In this paper this problem is considered as it is restricted to the class of planar graphs. Let G be a planar graph on n vertices and $s \in [0,n]$ be given. An s-partition of G is a partition of the vertex set of G into sets of size s and $n - s$. An optimals-partition is an s-partition that cuts the fewest number of edges. The main result of this paper is an algorithm that finds an optimal s-partition in time $O(b^2 n^3 2^{4.5b} )$, where b is the number of edges cut by an optimal s-partition. In particular, by letting $s = \lfloor n/2 \rfloor $ the immediate corollary that any planar graph with small $(O(\log n))$ bisection width may be bisected in polynomial time is obtained. Furthermore, suppose that a planar embedding $\hat G$ of G is also given such that the embedding of each biconnected component in $\hat G$ is at most m-outerplanar (such an embedding is called m-outerplane-separable). An algorithm for finding optimal s-partition of G in time $O(m^2 n^3 2^{3m} )$ is also given.

The via assignment problem, whose objective is to minimize the number of via columns used, is known to be NP-hard even when each net includes at most three vias. The authors develop efficient approximation algorithms for solving this problem. An algorithm for the case in which the size of each net is bounded by three is presented, and is then extended to the case in which the nets have arbitrary sizes.>

In this paper, we compare the performance of two popular graph bisection algorithms. We also present an empirical study of a new heuristic, first proposed in [B87], that dramatically improves the performance of these bisection algorithms on graphs with small (≤ 4) average degree.

We describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixed d⩾3, all suffciently large n and all b = o(n1-(1/[(d+1)/2]), the algorithm finds the minimum bisection for almost all d-regular labelled simple graphs with 2n nodes and bisection width b.