On local search for the generalized graph coloring problem

Given an edge-weighted graph and an integer k, the generalized graph coloring problem is the problem of partitioning the vertex set into k subsets so as to minimize the total weight of the edges that are included in a single subset. We recall a result on the equivalence between Karush-Kuhn-Tucker points for a quadratic programming formulation and local optima for the simple flip-neighborhood. We also show that the quality of local optima with respect to a large class of neighborhoods may be arbitrarily bad and that some local optima may be hard to find.     

Investigation of the Fitness Landscapes in Graph Bipartitioning: An Empirical Study

An empirical study is performed on the local-optimum space in graph bipartitioning. We examine some statistical features of the fitness landscape and the local properties of the landscape. They include the distributions of local optima, their cost-distance correlations, their attraction powers, the properties around the central area of local optima, etc. The study reveals some new notable results about the properties of the fitness landscape. For example, the central area yielded good quality in local-optimum space, the local-optimum space had the self-similar structure of global convexity, local optima showed clusters in more than one place, etc. We also provide a simple experiment on whether it is worth to exploit the area around the Euclidean center of the problem space.     

The acircuitic directed star arboricity of subcubic graphs is at most four

A directed star forest is a forest all of whose components are stars with arcs emanating from the center to the leaves. The acircuitic directed star arboricity of an oriented graph G (that is a digraph with no opposite arcs) is the minimum number of arc-disjoint directed star forests whose union covers all arcs of G and such that the union of any two such forests is acircuitic. We show that every subcubic graph has acircuitic directed star arboricity at most four.     

A class of heuristics for the constrained forest problem

The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a structured class of greedy heuristics for this NP-hard problem, and identify the best heuristic.     

Another greedy heuristic for the constrained forest problem

The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a greedy heuristic for this NP-hard problem, whose solutions are at least as good as, and often better than, those produced by the best-known 2-approximate heuristic.     

Minimum Spanning Table and Optimal Expansion of Competence Set

Each directed graph with asymmetric costs defined over its arcs can be represented by a matrix or table, called an expansion table. We explore first the basic properties of cycles and spanning tables of expansion tables, which correspond to the cycles and spanning trees of the directed graph. Then, we derive an algorithm to find a minimum spanning table which corresponds to a minimum spanning tree in the directed graph. Finally, we discuss how to use the algorithm to find the optimal competence set expansion and also discuss related problems.     

有限连通图上随机扩张森林和连通子图的边负相关性

设G为有限连通图．本文研究图G的子图空间G上的三类概率测度,它们分别刻画图的随机扩张树,随机扩张森林和随机连通子图．基于G上均匀扩张树的边负相关性,我们构造G上的一族边负相关的非平凡随机扩张森林和随机连通子图．此外,我们还给出一定条件下图上均匀扩张森林的边负相关性．     

Local search for the minimum label spanning tree problem with bounded color classes

In the Minimum Label Spanning Tree problem, the input consists of an edge-colored undirected graph, and the goal is to find a spanning tree with the minimum number of different colors. We investigate the special case where every color appears at most r times in the input graph. This special case is polynomially solvable for r=2, and NP- and APX-complete for any fixed r?3.We analyze local search algorithms that are allowed to switch up to k of the colors used in a feasible solution. We show that for k=2 any local optimum yields an (r+1)/2-approximation of the global optimum, and that this bound is tight. For every k?3, there exist instances for which some local optima are a factor of r/2 away from the global optimum.     

Decomposition of search for -structures in DAGs

We show that the problem of searching for v-structures in a directed acyclic graph can be decomposed into searches in its decomposed subgraphs. This result simplifies the search for v-structures and the recovery of local causal relationships.     

完全偶图的[1,2]因子计数

讨论了完全偶图存在[1,2]因子的充分必要条件，并给出了[1,2]因子的计数法。     

Relations between the Local Chromatic Number and Its Directed Version

The local chromatic number is a coloring parameter defined as the minimum number of colors that should appear in the most colorful closed neighborhood of a vertex under any proper coloring of the graph. Its directed version is the same when we consider only outneighborhoods in a directed graph. For digraphs with all arcs being present in both directions the two values are obviously equal. Here, we consider oriented graphs. We show the existence of a graph where the directed local chromatic number of all oriented versions of the graph is strictly less than the local chromatic number of the underlying undirected graph. We show that for fractional versions the analogous problem has a different answer: there always exists an orientation for which the directed and undirected values coincide. We also determine the supremum of the possible ratios of these fractional parameters, which turns out to be e, the basis of the natural logarithm.     

A branching greedoid for multiply-rooted graphs and digraphs

Two combinatorial structures which describe the branchings in a graph are graphic matroids and undirected branching greedoids. We introduce a new class of greedoids which connects these two structures. We also apply these greedoids to directed graphs to consider a matroid defined on a directed graph. Finally, we obtain a formula for the greedoid characteristic polynomial for multiply-rooted directed trees which can be determined from the vertices.     

Forest covers and a polyhedral intersection theorem

Aforest cover of a graph is a spanning forest for which each component has at least two nodes. We consider the convex hull of incidence vectors of forest covers in a graph and show that this polyhedron is the intersection of the forest polytope and the cover polytope. This polytope has both the spanning tree and perfect matching polytopes as faces. Further, the forest cover polytope remains integral with the addition of the constraint requiring that, for some integerk, exactlyk edges be used in the solution.Research done while thae authors were visiting the Institut für Ökonometrie und Operations Research, Universität Bonn, West Germany.Financial support provided by the Natural Sciences and Engineering Research Council, Canada and the German Research Association (Deutsche Forschungsgemeneinschaft, SFB 303).     

Local Unstable Entropy and Local Unstable Pressure for Partially Hyperbolic Endomorphisms*

In this paper, local unstable metric entropy, local unstable topological entropy and local unstable pressure for partially hyperbolic endomorphisms are introduced and investigated. Specially, two variational principles concerning relationships among the above mentioned numbers are formulated.     

Optimum matching forests I: Special weights

We introduce the concept of matching forests as a generalization of branchings in a directed graph and matchings in an undirected graph. Given special weights on the edges of a mixed graph, we present an efficient algorithm for finding an optimum weight-sum matching forest. The algorithm is a careful application of known branching and matching algorithms. The maximum cardinality matching forest problem is solved as a special case.Research partially supported by a N.R.C. of Canada Postdoctorate Fellowship.     

On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives

The structure of the search space explains the behavior of multiobjective search algorithms, and helps to design well-performing approaches. In this work, we analyze the properties of multiobjective combinatorial search spaces, and we pay a particular attention to the correlation between the objective functions. To do so, we extend the multiobjective NK-landscapes in order to take the objective correlation into account. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives, and the objective correlation on the structure of the Pareto optimal set, in terms of cardinality and number of supported solutions, as well as on the number of Pareto local optima. This work concludes with guidelines for the design of multiobjective local search algorithms, based on the main fitness landscape features.     

冠状系统的R-旋转图与(R)-旋转图

冠状系统Hc的R(R)-旋转变换是指对Hc的一个完美匹配M,同时将Hc中所有正常(非正常)M-交错的六边形变换为非正常(正常)M-交错的六边形,从而得到Hc的另一个完美匹配的变换.通过这两种旋转变换可分别建立Hc完美匹配集上的层次结构,分别称为R-旋转图和R-旋转图,记为R(Hc)和R(Hc).已经证明知道R(Hc)是有向森林,其每个分支都为有向根树.首先讨论了冠状系统的Z-变换有向图与其R-旋转图之间的关系,指出按连通分支对这两种图的顶点集进行划分,其结果一样.在此基础上,证明了R(Hc)的任一分支T(有向根树)都对应R(Hc)的一个分支T,且两者的顶点集相同,进而证明了T与(T)具有相同的高度和宽度.     

On arc-traceable local tournaments

A digraph D is arc-traceable if for every arc xy of D, the arc xy belongs to a directed Hamiltonian path of D. A local tournament is an oriented graph such that the negative neighborhood as well as the positive neighborhood of every vertex induces a tournament. It is well known that every tournament contains a directed Hamiltonian path and, in 1990, Bang-Jensen showed the same for connected local tournaments. In 2006, Busch, Jacobson and Reid studied the structure of tournaments that are not arc-traceable and consequently gave various sufficient conditions for tournaments to be arc-traceable. Inspired by the article of Busch, Jacobson and Reid, we develop in this paper the structure necessary for a local tournament to be not arc-traceable. Using this structure, we give sufficient conditions for a local tournament to be arc-traceable and we present examples showing that these conditions are best possible.     

Size of monochromatic components in local edge colorings

An edge coloring of a graph is a local r coloring if the edges incident to any vertex are colored with at most r distinct colors. We determine the size of the largest monochromatic component that must occur in any local r coloring of a complete graph or a complete bipartite graph.