CHECKCOL: Improved local search for graph coloring

In this paper we present a novel coloring algorithm based on local search. We analyze its performance, and report several experimental results on DIMACS benchmark graphs. From our experiments, this algorithm looks robust, and yields a substantial speed up on previous algorithms for coloring. Our algorithm improves the best known coloring for four different DIMACS benchmark graphs: namely, Le450-25c, Le450-25d and Flat300_28_0 and Flat1000_76_0. Furthermore, we have run experiments on a simulator to get insights on its cache consciousness: from these experiments, it appears that the algorithm performs substantially less cache misses than other existing algorithms.     

Geometric automorphism groups of graphs

Constructing symmetric drawings of graphs is NP-hard. In this paper, we present a new method for drawing graphs symmetrically based on group theory. More formally, we define an n-geometric automorphism group as a subgroup of the automorphism group of a graph that can be displayed as symmetries of a drawing of the graph in n dimensions. Then we present an algorithm to find all 2- and 3-geometric automorphism groups of a given graph. We implement the algorithm using Magma [〈http://magma.maths.usyd.edu.au〉] and the experimental results show that our approach is very efficient in practice. We also present a drawing algorithm to display 2- and 3-geometric automorphism groups.     

Equivalence-free exhaustive generation of matroid representations

In this paper we present an algorithm for the problem of exhaustive equivalence-free generation of 3-connected matroids which are represented by a matrix over some finite (partial) field, and which contain a given minor. The nature of this problem is exponential, and it appears to be much harder than, say, isomorph-free generation of graphs. Still, our algorithm is very suitable for practical use, and it has been successfully implemented in our matroid computing package MACEK [http://www.mcs.vuw.ac.nz/research/macek, 2001-05].     

Convex drawings of hierarchical planar graphs and clustered planar graphs

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43–69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a “fully convex drawing,” a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.     

Hom complexes and hypergraph colorings

Babson and Kozlov (2006) [2] studied Hom-complexes of graphs with a focus on graph colorings. In this paper, we generalize Hom-complexes to r-uniform hypergraphs (with multiplicities) and study them mainly in connection with hypergraph colorings. We reinterpret a result of Alon, Frankl and Lovász (1986) [1] by Hom-complexes and show a hierarchy of known lower bounds for the chromatic numbers of r-uniform hypergraphs (with multiplicities) using Hom-complexes.     

A hybrid heuristic algorithm for the open-pit-mining operational planning problem

This paper deals with the Open-Pit-Mining Operational Planning problem with dynamic truck allocation. The objective is to optimize mineral extraction in the mines by minimizing the number of mining trucks used to meet production goals and quality requirements. According to the literature, this problem is NP-hard, so a heuristic strategy is justified. We present a hybrid algorithm that combines characteristics of two metaheuristics: Greedy Randomized Adaptive Search Procedures and General Variable Neighborhood Search. The proposed algorithm was tested using a set of real-data problems and the results were validated by running the CPLEX optimizer with the same data. This solver used a mixed integer programming model also developed in this work. The computational experiments show that the proposed algorithm is very competitive, finding near optimal solutions (with a gap of less than 1%) in most instances, demanding short computing times.     

Small maximal matchings of random cubic graphs

We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random n‐vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximal matching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623n. We also give an existence proof which shows that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. less than 0.3214n. It is known that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. larger than 0.3158n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 293–323, 2009     

Minimum independent dominating sets of random cubic graphs

We present a heuristic for finding a small independent dominating set ?? of cubic graphs. We analyze the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations, and obtain an upper bound on the expected size of ??. A corresponding lower bound is derived by means of a direct expectation argument. We prove that ?? asymptotically almost surely satisfies 0.2641n ≤ |??| ≤ 0.27942n. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 147–161, 2002     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

Memetic algorithm for the antibandwidth maximization problem

The antibandwidth maximization problem (AMP) consists of labeling the vertices of a n-vertex graph G with distinct integers from 1 to n such that the minimum difference of labels of adjacent vertices is maximized. This problem can be formulated as a dual problem to the well known bandwidth problem. Exact results have been proved for some standard graphs like paths, cycles, 2 and 3-dimensional meshes, tori, some special trees etc., however, no algorithm has been proposed for the general graphs. In this paper, we propose a memetic algorithm for the antibandwidth maximization problem, wherein we explore various breadth first search generated level structures of a graph—an imperative feature of our algorithm. We design a new heuristic which exploits these level structures to label the vertices of the graph. The algorithm is able to achieve the exact antibandwidth for the standard graphs as mentioned. Moreover, we conjecture the antibandwidth of some 3-dimensional meshes and complement of power graphs, supported by our experimental results.     

An approach for the Steiner problem in directed graphs

We present a scheme to solve the Steiner problem in directed graphs using a heuristic method to obtain upper bounds and thek shortest arborescences algorithm to compute lower bounds. We propose to combine these ideas in an enumerative algorithm. Computational results are presented for both thek shortest arborescences algorithm and the heuristic method, including reduction tests for the problem.This work was partially supported by CNP_q, FINEP, CAPES and IBM do Brasil.     

A fast local search method for minimum energy broadcast in wireless ad hoc networks

Local search methods are often used to reduce the power consumption of broadcast routing in wireless networks. For a classic method, sweep, the best available time complexity result is O(|V|⁴). We present an O(|V|²)-time method, which exhaustively removes unnecessary transmissions yielding a solution comparable to that of sweep.     

A primer on disease mapping and ecological regression using {\texttt{INLA}}

Spatial and spatio-temporal disease mapping models are widely used for the analysis of registry data and usually formulated in a hierarchical Bayesian framework. Explanatory variables can be included by a so-called ecological regression. It is possible to assume both a linear and a nonparametric association between disease incidence and the explanatory variable. Integrated nested Laplace approximations (INLA) can be used as a tool for Bayesian inference. INLA is a promising alternative to Markov chain Monte Carlo (MCMC) methods which provides very accurate results within short computational time. It is shown in this paper, how parameter estimates for well-known spatial and spatio-temporal models can be obtained by running INLA directly in R{\texttt{R}} using the package INLA{\texttt{INLA}}. Selected R{\texttt{R}} code is shown. An emphasis is given to the inclusion of an explanatory variable. Cases of Coxiellosis among Swiss cows from 2005 to 2008 are used for illustration. The number of stillborn calves is included as time-varying covariate. Additionally, various aspects of INLA such as model choice criteria, computer time, accuracy of the results and usability of the R{\texttt{R}} package are discussed.     

Solving the Minimum Weighted Integer Coloring Problem

In this paper, we present, as we are aware of, the first combinatorialalgorithm specifically designed for the minimum weighted integercoloring problem (MWIP). We test the algorithm on randomly generated graphs with integer weights uniformly drawn from intervals [1, 1], [1, 2], [1, 5], [1, 10], [1, 15], and [1, 20]. We also use theproposed algorithm to test the quality of a simple, yet effectiveheuristic for the MWIP in the literature. We have observed from our test that: i( the algorithm is able to solve MWIP on graphs of up to 20 vertices when the average vertex weights is not too large; ii( The relative gap between the simple heuristic solutions and the optimal solution seems to decrease as the average vertex weight increases. A rough comparison with the state-of-the-art methods for the minimum unweighted coloring problem seems to suggest the advantage of solving MWIP directly.     

Efficient orthogonal matrix polynomial based method for computing matrix exponential

The matrix exponential plays a fundamental role in the solution of differential systems which appear in different science fields. This paper presents an efficient method for computing matrix exponentials based on Hermite matrix polynomial expansions. Hermite series truncation together with scaling and squaring and the application of floating point arithmetic bounds to the intermediate results provide excellent accuracy results compared with the best acknowledged computational methods. A backward-error analysis of the approximation in exact arithmetic is given. This analysis is used to provide a theoretical estimate for the optimal scaling of matrices. Two algorithms based on this method have been implemented as MATLAB functions. They have been compared with MATLAB functions funm and expm obtaining greater accuracy in the majority of tests. A careful cost comparison analysis with expm is provided showing that the proposed algorithms have lower maximum cost for some matrix norm intervals. Numerical tests show that the application of floating point arithmetic bounds to the intermediate results may reduce considerably computational costs, reaching in numerical tests relative higher average costs than expm of only 4.43% for the final Hermite selected order, and obtaining better accuracy results in the 77.36% of the test matrices. The MATLAB implementation of the best Hermite matrix polynomial based algorithm has been made available online.     

Differentiation of generalized inverses for rational and polynomial matrices

Our basic motivation is a direct method for computing the gradient of the pseudo-inverse of well-conditioned system with respect to a scalar, proposed in [13] by Layton. In the present paper we combine the Layton’s method together with the representation of the Moore-Penrose inverse of one-variable polynomial matrix from [24] and developed an algorithm for computing the gradient of the Moore-Penrose inverse for one-variable polynomial matrix. Moreover, using the representation of various types of pseudo-inverses from [26], based on the Grevile’s partitioning method, we derive more general algorithms for computing {1}, {1, 3} and {1, 4} inverses of one-variable rational and polynomial matrices. Introduced algorithms are implemented in the programming language MATHEMATICA. Illustrative examples on analytical matrices are presented.     

Cancellation properties in ideal systems: A classification of e.a.b. semistar operations

We give a classification of e.a.b. semistar (and star) operations by defining four different (successively smaller) distinguished classes. Then, using a standard notion of equivalence of semistar (and star) operations to partition the collection of all e.a.b. semistar (or star) operations, we show that there is exactly one operation of finite type in each equivalence class and that this operation has a range of nice properties. We give examples to demonstrate that the four classes of e.a.b. semistar (or star) operations we defined can all be distinct. In particular, we solve the open problem of showing that a.b. is really a stronger condition than e.a.b.     

Register Allocation in Structured Programs

In this article we look at the register allocation problem. In the literature this problem is frequently reduced to the general graph coloring problem and the solutions to the problem are obtained from graph coloring heuristics. Hence, no algorithm with a good performance guarantee is known. Here we show that when attention is restricted tostructured programswhich we define to be programs whose control-flow graphs are series-parallel, there is an efficient algorithm that produces a solution which is within a factor of 2 of the optimal solution. We note that even with the previous restriction the resulting coloring problem is NP-complete.We also consider how to delete a minimum number of edges from arbitrary control-flow graphs to make them series-parallel and to apply our algorithm. We show that this problem is Max SNP hard. However, we define the notion of anapproximate articulation pointand we give efficient algorithms to find approximate articulation points. We present a heuristic for the edge deletion problem based on this notion which seems to work well when the given graph is close to series-parallel.     

Perfect and locally perfect colorings

We present a new algorithm for coloring perfect graphs and use it to color the parity orderable graphs, a class which strictly contains parity graphs. Also, we modify this algorithm to obtain an O(m² + n) locally perfect coloring algorithm for parity graphs. © 1995 John Wiley & Sons, Inc.