On graphs of maximum size with given girth and order
- Authors: Miller, Mirka , Lin, Yuqing , Brankovic, Ljiljana , Tang, Jianmin
- Date: 2006
- Type: Text , Conference paper
- Relation: Paper presented at AWOCA 2006, 17th Australasian Workshop on Combinatorial Algorithms, Uluru, Australia : 13th July, 2006
- Full Text: false
- Reviewed:
- Description: E1
- Description: 2003001918
An open problem : (4; g)-cages with odd g <= 5 are tightly connected
- Authors: Tang, Jianmin , Balbuena, Camino , Lin, Yuqing , Miller, Mirka
- Date: 2007
- Type: Text , Conference paper
- Relation: Paper presented at Thirteenth Computing : The Australasian Theory Symposium, CATS2007, Ballarat, Victoria : January 30th-Febuary 2nd p. 141-144
- Full Text: false
- Description: Interconnection networks form an important area which has received much attention, both in theoretical research and in practice. From theoretical point of view, an interconnection network can be modelled by a graph, where the vertices of the graph represent the nodes of the network and the edges of the graph represent connections between the nodes in the network. Fault tolerance is an important performance feature when designing a network, and the connectivity of the underlying graph is one of the measures of fault tolerance for a network. A graph is connected if there is a path between any two vertices of G. We say that G is t-connected if the deletion of at least t vertices of G is required to disconnect the graph. A graph with minimum degree delta is maximally connected if it is delta-connected. A graph is superconnected if its only minimum disconnecting sets are those induced by the neighbors of a vertex; a graph is said to be tightly superconnected if (i) any minimum disconnecting set is the set of neighbors of a single vertex; and (ii) the deletion of a minimum disconnecting set results in a graph with two components (one of which has only one vertex, another component is a connected graph). A (delta; g) - cage is a delta-regular graph with girth g and with the least possible number of vertices. In this paper we consider the problem of whether or not (4; g)-cages for g >= 5 are tightly superconnected. We present some partial results and the remaining open problems.
- Description: Interconnection networks form an important area which has received much attention, both in theoretical research and in practice. From theoretical point of view, an interconnection network can be modelled by a graph, where the vertices of the graph represent the nodes of the network and the edges of the graph represent connections between the nodes in the network. Fault tolerance is an important performance feature when designing a network, and the connectivity of the underlying graph is one of the measures of fault tolerance for a network. A graph is connected if there is a path between any two vertices of G. We say that G is t-connected if the deletion of at least t vertices of G is required to disconnect the graph. A graph with minimum degree \delta\ is maximally connected if it is \delta\-connected. A graph is superconnected if its only minimum disconnecting sets are those induced by the neighbors of a vertex; a graph is said to be tightly superconnected if (i) any minimum disconnecting set is the set of neighbors of a single vertex; and (ii) the deletion of a minimum disconnecting set results in a graph with two components (one of which has only one vertex, another component is a connected graph). A (\delta\; g) - cage is a \delta\-regular graph with girth g and with the least possible number of vertices. In this paper we consider the problem of whether or not (4; g)-cages for g >= 5 are tightly superconnected. We present some partial results and the remaining open problems.
- Description: 2003005018
Calculating the extremal number ex (v ; {C3, C4, ..., Cn})
- Authors: Tang, Jianmin , Lin, Yuqing , Miller, Mirka
- Date: 2006
- Type: Text , Journal article
- Relation: Electronic Notes in Discrete Mathematics Vol. 27, no. (2006), p. 101-102
- Full Text: false
- Reviewed:
- Description: This paper introduces and analyzes a parallel method of simulated annealing. Borrowing from genetic algorithms, an effective combination of simulated annealing and genetic algorithms, called parallel recombinative simulated annealing, is developed. This new algorithm strives to retain the desirable asymptotic convergence properties of simulated annealing, while adding the populations approach and recombinative power of genetic algorithms. The algorithm iterates a population of solutions rather than a single solution, employing a binary recombination operator as well as a unary neighborhood operator. Proofs of global convergence are given for two variations of the algorithm. Convergence behavior is examined, and empirical distributions are compared to Boltzmann distributions. Parallel recombinative simulated annealing is amenable to straightforward implementation on SIMD, MIMD, or shared-memory machines. The algorithm, implemented on the CM-5, is run repeatedly on two deceptive problems to demonstrate the added implicit parallelism and faster convergence which can result from larger population sizes.
- Description: C1
Hybrid simulated annealing and genetic algorithm for degree/diameter problem
- Authors: Tang, Jianmin , Miller, Mirka , Lin, Yuqing
- Date: 2005
- Type: Text , Conference paper
- Relation: Paper pesented at Sixteenth Australasian Workshop on Combinatorial Algorithms, AWOCA 2005, Ballarat, Victoria : 18th-21st September 2005 p. 321-331
- Full Text: false
- Description: The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. This paper deals with directed graphs. General upper bounds, called Moore bounds, exist for the largest possible order of such digraphs of maximum degree d and diameter k. It is known that simulated annealing and genetic algorithm are effective techniques to identify global optimization solutions. This paper describes our attempt to build a Hybrid Simulated Annealing and Genetic Algorithm (HSAGA) that can be used to construct larger digraphs, and displays our preliminary results obtained by HSAGA.
- Description: 2003001438
HSAGA and its application for the construction of near-Moore digraphs
- Authors: Tang, Jianmin , Miller, Mirka , Lin, Yuqing
- Date: 2008
- Type: Text , Journal article
- Relation: Journal of Discrete Algorithms Vol. 6, no. 1 (2008), p. 73-84
- Full Text: false
- Reviewed:
- Description: The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. This paper deals with directed graphs. General upper bounds, called Moore bounds, exist for the largest possible order of such digraphs of maximum degree d and given diameter k. It is known that simulated annealing and genetic algorithm are effective techniques to identify global optimal solutions. This paper describes our attempt to build a Hybrid Simulated Annealing and Genetic Algorithm (HSAGA) that can be used to construct large digraphs. We present our new results obtained by HSAGA, as well as several related open problems. © 2007 Elsevier B.V. All rights reserved.
- Description: C1