ColoringCaramia M, Dell'Olmo p journal of heuristics




НазваниеColoringCaramia M, Dell'Olmo p journal of heuristics
страница1/3
Дата06.10.2012
Размер73.9 Kb.
ТипДокументы
  1   2   3
Elsevier Science Direct

Keyword: graph coloring


  1. Constraint propagation in graph coloringCaramia M, Dell'Olmo P
    JOURNAL OF HEURISTICS 8 (1): 83-107 JAN 2002

In this paper we propose a method for integrating constraint propagation algorithms into an optimization procedure for vertex coloring with the goal of finding improved lower bounds. The key point we address is how to get instances of Constraint Satisfaction Problems (CSPs) from a graph coloring problem in order to give rise to new lower bounds outperforming the maximum clique bound. More precisely, the algorithms presented have the common goal of finding CSPs in the graph for which infeasibility can be proven. This is achieved by means of constraint propagation techniques which allow the algorithms to eliminate inconsistencies in the CSPs by updating domains dynamically and rendering such infeasibilities explicit. At the end of this process we use the largest CSP for which it has not been possible to prove infeasibility as an input for an algorithm which enlarges such CSP to get a feasible coloring. We experimented with a set of middle-high density graphs with quite a large difference between the maximum clique and the chromatic number


  1. Semi-definite positive programming relaxations for graph K-n-coloring in frequency assignment Meurdesoif P, Rottembourg B
    RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH 35 (2): 211-228 APR-JUN 2001

In this paper we will describe a now class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct n-uples of colors used to color a given set of n-complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible solutions with a probabilistic approach.



  1. The fundamental class of a rational space, the graph coloring problem and other classical decision problems Lechuga L, Murillo A
    BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN 8 (3): 451-467 JUL-SEP 2001

The problem of k-coloring a graph is equivalent to deciding whether a particular cohomology class of a certain rational space vanishes. Although this problem is NP-hard we are able to construct a fast (polynomial) algorithm to give. a representative of this class. We also associate to other classical decision problems rational spaces so that the given problem has a solution if and only if the associated space is not elliptic. As these spaces have null Euler homotopy characteristic we easily characterize when the given problem has a solution in terms of commutative algebra.


  1. Extending graph colorings using no extra colors Albertson MO, Moore EH
    DISCRETE MATHEMATICS 234 (1-3): 125-132 MAY 6 2001

Suppose the graph G can be r-colored using colors 1,2,...,r, so that no vertex is adjacent to two vertices colored r. If P subset of V(G) is such that the distance between any two vertices in P is at least 12, then any r-coloring of P extends to an r-coloring of all of G. If there exists an r-coloring of G in which the distance between vertices colored r is at least 4 (resp. 6), then any r-coloring of P extends to an r-coloring of all of G provided the distance between any two vertices in P is at least 8 (resp. 6). Similar results hold if P induces a set of cliques. This continues previous work of the authors (Albertson and Moore, J. Combin. Theory Ser. B 77 (1999) 83.) on extending (r + 1)-colorings of r-chromatic graphs. Examples show that the distance constraints on P are almost sharp. We show that triangle-free outerplanar graphs instantiate our results and speculate on other families of graphs that might have r-color extension theorems. (C) 2001 Elsevier Science B.V. All rights reserved.


  1. Oriented graph coloring Sopena E
    DISCRETE MATHEMATICS 229 (1-3): 359-369 FEB 28 2001

An oriented k-coloring of an oriented graph G (that is a digraph with no cycle of length 2) is a partition of its vertex set into k subsets such that (i) no two adjacent vertices belong to the same subset and (ii) all the arcs between any two subsets have the same direction. We survey the main results that have been obtained on oriented graph colorings. (C) 2001 Elsevier Science B.V. All rights reserved


  1. Graph coloring and reverse mathematicsSchmerl JH
    MATHEMATICAL LOGIC QUARTERLY 46 (4): 543-548 2000

Improving a theorem of Gasarch and Hirst, we prove that if 2 less than or equal to k less than or equal to m less than or equal to omega, then the following is equivalent to WKL0 over RCA(0): Every locally k-colorable graph is m-colorable



  1. A minimal-state processing search algorithm for graph coloring problems
    Funabiki N, Higashino T
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E83A (7): 1420-1430 JUL 2000

This paper presents a heuristic graph coloring algorithm named MIPS_CLR, a MInimal-state Processing Search algorithm for the graph CoLoRing problem. Given a graph G(V, E), the goal of this NP-complete problem is to find a color assignment to every vertex in II such that arty pair of adjacent vertices must not receive the same color but also the total number of colors should be minimized. The graph coloring problem has been widely studied due to its large number of practical applications in various fields. In MIPS-CLR, a construction stage first generates an initial minimal state composed of as many as: colored vertices by a simple greedy algorithm, after a maximal clique of G is found by a maximum clique algorithm. Then, a refinement stage iteratively seeks a solution state while keeping minimality in terms of a cost function by a minimal-state transition method. In this method, the schemes of a best color selection, a random color selection, a color assignment shuffle, and a gradual color expansion are used together to realize the discrete descent starch with hill-climbing capabilities. The performance of MIPS_CLR is evaluated through solving DIMACS benchmark graph instances, where the solution quality is generally better than existing algorithms while the computation time is comparable with the Lest existing one. In particular, MIPS-CLR provides new lower bound solutions for several instances. The simulation results, confirm the extensive search capability of our MIPS_CLR approach For the graph coloring problem


  1. Graph coloring algorithmsZhou X, Nishizeki T
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E83D (3): 407-417 MAR 2000

Graph coloring is a fundamental problem, which often appears in various scheduling problems like the file transfer problem on computer networks. In this paper, we survey recent advances and results oil the edge-coloring, the f-coloring, the [g,f]-coloring, and the total coloring problem for various classes of graphs such as bipartite graphs, series-parallel graphs, planar graphs, and graphs: having fixed degeneracy, tree-width, genus, arboricity, unicyclic index or thickness. In particular, we review various upper bounds on the minimum numbers of colors required to color these classes of graphs, and present efficient sequential and parallel algorithms to find colorings of graphs with these numbers of colors.


  1. Partial list coloringsAlbertson MO, Grossman S, Haas R
    DISCRETE MATHEMATICS 214 (1-3): 235-240 MAR 21 2000

Suppose G is an s-choosable graph with n vertices, and every vertex of G is assigned a list of t colors. We conjecture that at least (t/s)n of the vertices of G can be colored from these lists. We provide lower bounds and consider related questions. For instance, we show that if G is chi-colorable (rather than being s-choosable), then more than (1 - ((chi - 1)/chi)(t))n of the vertices of G can be colored from the lists and that this is asymptotically best possible. We include a number of open questions. (C) 2000 Elsevier Science B.V. All rights reserved


  1. A simple competitive graph coloring algorithm Kierstead HA
    JOURNAL OF COMBINATORIAL THEORY SERIES B 78 (1): 57-68 JAN 2000

We prove that the game coloring number, and therefore the game chromatic number, of a planar graph is at most 18. This is a slight improvement of the current upper bound of 19. Perhaps more importantly, we bound the game coloring number of a graph G in terms of a new parameter, (G). We use this result to give very easy proofs of the best known upper bounds on game coloring number for forests, interval graphs, chordal graphs, outerplanar graphs, and line graphs and to give a new upper bound on the game coloring number of graphs embeddable on orientable surfaces with bounded genus. (C) 2000 Academic Press.

  1. Hybrid evolutionary algorithms for graph coloring Galinier P, Hao JK
    JOURNAL OF COMBINATORIAL OPTIMIZATION 3 (4): 379-397 DEC 1999

A recent and very promising approach for combinatorial optimization is to embed local search into the framework of evolutionary algorithms. In this paper, we present such hybrid algorithms for the graph coloring problem. These algorithms combine a new class of highly specialized crossover operators and a well-known tabu search algorithm. Experiments of such a hybrid algorithm are carried out on large DIMACS Challenge benchmark graphs. Results prove very competitive with and even better than those of state-of-the-art algorithms. Analysis of the behavior of the algorithm sheds light on ways to further improvement


  1. Three-quarter approximation for the number of unused colors in graph coloring Tzeng WG, King GH
    INFORMATION SCIENCES 114 (1-4): 105-126 MAR 1999

The graph coloring problem is to color vertices of a graph so that no adjacent vertices are of the same color. The problem is difficult not only in finding the optimal solution, but also in approximation. Since it is hard to approximate the minimum number of colors, we consider to approximate the maximum number of unused colors. This approximation is based on saving colors with respect to the most naive coloring method, which colors each vertex with a different color. In this paper we propose a polynomial-time graph coloring algorithm with approximation ratio 3/4 for the maximum number of unused colors, which improves the previous result 2/3. (C) 1999 Elsevier Science Inc. All rights reserved.


  1. Graph coloring with adaptive evolutionary algorithms Eiben AE, Van der Hauw JK, Van Hemert JI
    JOURNAL OF HEURISTICS 4 (1): 25-46 JUN 1998

This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EAs). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping Genetic Algorithm (GGA) on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping (GA) and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity


  1. An adaptive, multiple restarts neural network algorithm for graph coloring Jagota A
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 93 (2): 257-270 SEP 6 1996

The graph coloring problem is amongst the most difficult ones in combinatorial optimization, with a diverse set of significant applications in science and industry. Previous neural network attempts at coloring graphs have not worked well. In particular, they do not scale up to large graphs. Furthermore, experimental evaluations on real-world graphs have been lacking, and so have comparisons with state of the art conventional algorithms. In this paper we address all of these issues. We develop an improved neural network algorithm for graph coloring that scales well with graph size. The algorithm employs multiple restarts, and adaptively reduces the network's size from restart to restart as it learns better ways to color a given graph. Hence it gets faster and leaner as it evolves. We evaluate this algorithm on a structurally diverse set of graphs that arise in different applications. We compare its performance with that of a state of the art conventional algorithm on identical graphs. The conventional algorithm works better overall, though ours is not far behind. Ours works better on some graphs. The inherent parallel and distributed nature of our algorithm, especially within a neural network architecture, is a potential advantage for implementation and speed up.


  1. Genetic and hybrid algorithms for graph coloring Fleurent C, Ferland JA
    ANNALS OF OPERATIONS RESEARCH 63: 437-461 1996

Some genetic algorithms are considered for the graph coloring problem. As is the case for other combinatorial optimization problems, pure genetic algorithms are outperformed by neighborhood search heuristic procedures such as tabu search. Nevertheless, we examine the performance of several hybrid schemes that can obtain solutions of excellent quality. For some graphs, we illustrate that genetic operators can fulfill long-term strategic functions for a tabu search implementation that is chiefly founded on short-term memory strategies.


  1. Graph-coloring result and its consequences for polygon-guarding problems Hoffmann F, Kriegel K
    SIAM JOURNAL ON DISCRETE MATHEMATICS 9 (2): 210-224 MAY 1996

The following graph-coloring result is proved: let G be a 2-connected, bipartite, and plane graph. Then one can triangulate G in such a way that the resulting graph is 3-colorable. Such a triangulation can be computed in O(n(2)) time. This result implies several new upper bounds for polygon guarding problems, including the first nontrivial upper bound for the rectilinear prison yard problem. (1) [n/3] vertex guards are sufficient to watch the interior of a rectilinear polygon with holes. (2) [5n/12] + 3 vertex guards ([n+4/3] point guards) are sufficient to simultaneously watch both the interior and exterior of a rectilinear polygon. Moreover, a new lower bound of [5n/16] vertex guards for the rectilinear prison yard problem is shown and proved to be asymptotically tight for the class of orthoconvex polygons


  1. A BLOW-UP CONSTRUCTION AND GRAPH-COLORING ALUFFI P
    DISCRETE MATHEMATICS 145 (1-3): 11-35 OCT 13 1995

Given a graph G (or more generally a matroid embedded in a projective space), we construct a sequence of algebraic varieties whose geometry encodes combinatorial information about G. For example, the chromatic polynomial of G can be computed as an intersection product of certain classes on these varieties, or recovered in terms of the Segre classes of related sub-schemes of P ''; other information such as Crape's invariant also finds a very natural geometric counterpart. The note presents this construction, and gives 'geometric' proofs of a number of standard combinatorial results on the chromatic polynomial and Crape's invariant


  1. A RANDOMIZED ALGORITHM FOR K-COLORABILITY ZEROVNIK J
    DISCRETE MATHEMATICS 131 (1-3): 379-393 AUG 5 1994

This note is a report of testing a straightforward generalization of the randomized 3-coloring algorithm of Petford and Welsh (1989) on the decision problems of 4- and 10-coloring. We observe similar behavior, namely the existence of critical regions. Experimentally, the average time complexity for large n again seems to grow slowly, although in some cases the number of transitions needed is prohibitively high for practical applications.


  1. PERIODIC ASSIGNMENT AND GRAPH-COLORING KORST J, AARTS E, LENSTRA JK, WESSELS J
    DISCRETE APPLIED MATHEMATICS 51 (3): 291-305 JUL 6 1994

We analyse the problem of executing periodic operations on a minimum number of identical processors under different constraints. The analysis is based on a reformulation of the problem in terms of graph colouring. It is shown that different constraints result in colouring problems defined on different classes of graphs, viz. interval graphs, circular-arc graphs and periodic-interval graphs. We discuss the complexity of these colouring problems in detail.


Web of Science


Keyword: Graph coloring


References


2002


  1. Dense critical and vertex-critical graphs, Discrete Mathematics, In Press, Uncorrected Proof, Available online 2 April 2002,
    Tommy R. Jensen


This paper gives new constructions of k-chromatic critical graphs with high minimum degree and high edge density, and of vertex-critical graphs with high edge density


  1. On the divisibility of graphs, Discrete Mathematics, Volume 242, Issues 1-3, 6 January 2002, Pages 145-156
    Chính T. Hoàng and Colin McDiarmid


A graph G is k-divisible if for each induced subgraph H of G with at least one edge, there is a partition of the vertex set of H into sets V1,...,Vk such that no Vi contains a maximum clique of H. We show that a claw-free graph is 2-divisible if and only if it does not contain an odd hole: we conjecture that this result is true for any graph, and present further conjectures relating 2-divisibility to the strong perfect graph conjecture. We also present related results involving the chromatic number and the stability number, with connections to Ramsey theory


2001


  1. Extending graph colorings using no extra colors, Discrete Mathematics, Volume 234, Issues 1-3, 6 May 2001, Pages 125-132
    Michael O. Albertson and Emily H. Moore


Suppose the graph G can be r-colored using colors 1,2,...,r, so that no vertex is adjacent to two vertices colored r. If PV(G) is such that the distance between any two vertices in P is at least 12, then any r-coloring of P extends to an r-coloring of all of G. If there exists an r-coloring of G in which the distance between vertices colored r is at least 4 (resp. 6), then any r-coloring of P extends to an r-coloring of all of G provided the distance between any two vertices in P is at least 8 (resp. 6). Similar results hold if P induces a set of cliques. This continues previous work of the authors (Albertson and Moore, J. Combin. Theory Ser. B 77 (1999) 83.) on extending (r+1)-colorings of r-chromatic graphs. Examples show that the distance constraints on P are almost sharp. We show that triangle-free outerplanar graphs instantiate our results and speculate on other families of graphs that might have r-color extension theorems


  1. Oriented graph coloring, Discrete Mathematics, Volume 229, Issues 1-3, 28 February 2001, Pages 359-369
    Eric Sopena


An oriented k-coloring of an oriented graph G (that is a digraph with no cycle of length 2) is a partition of its vertex set into k subsets such that (i) no two adjacent vertices belong to the same subset and (ii) all the arcs between any two subsets have the same direction. We survey the main results that have been obtained on oriented graph colorings.

2000


  1. On simultaneous colorings of embedded graphs, Discrete Mathematics, Volume 224, Issues 1-3, 28 September 2000, Pages 207-214
    Daniel P. Sanders and John Maharry

In this paper, it is shown that if the maximum degree of a graph is large relative to the genus of the embedding than the edge-face chromatic number of the graph is at most +1 and its vertex-edge-face chromatic number is at most +2. Both results are best possible


  1. On small uniquely vertex-colourable graphs and Xu's conjecture, Discrete Mathematics, Volume 223, Issues 1-3, 28 August 2000, Pages 93-108
    Amir Daneshgar and Reza Naserasr


Consider the parameter for a k-chromatic graph G, on the set of vertices V(G) and with the set of edges E(G). It is known that (G)0 for any k-chromatic uniquely vertex-colourable graph G (k-UCG), and, S.J. Xu has conjectured that for any k-UCG, G, (G)=0 implies that cl(G)=k; in which cl(G) is the clique number of G. In this paper, first, we introduce the concept of the core of a k-UCG as an induced subgraph without any colour-class of size one, and without any vertex of degree k-1. Considering (k,n)-cores as k-UCGs on n vertices, we show that edge-minimal (k,2k)-cores do not exist when k3, which shows that for any edge-minimal k-UCG on 2k vertices either the conjecture is true or there exists a colour-class of size one. Also, we consider the structure of edge-minimal (k,2k+1)-cores and we show that such cores exist for all k4. Moreover, we characterize all edge-minimal (4,9)-cores and we show that there are only seven such cores (up to isomorphism). Our proof shows that Xu's conjecture is true in the case of edge-minimal (4,9)-cores


  1. Variable degeneracy: extensions of Brooks' and Gallai's theorems, Discrete Mathematics, Volume 214, Issues 1-3, 21 March 2000, Pages 101-112
    O. V. Borodin, A. V. Kostochka and B. Toft


We introduce the concept of variable degeneracy of a graph extending that of k-degeneracy. This makes it possible to give a common generalization of the point partition numbers and the list chromatic number. In particular, the list point arboricity of a graph is considered. We extend Brooks' and Gallai's theorems in terms of covering the vertices of a graph by disjoint induced subgraphs G1,...,Gs such that Gi is strictly fi-degenerate, given nonnegative-integer-valued functions f1,...,fs whose sum is bounded below at each vertex by the degree of that vertex.


  1   2   3

Похожие:

ColoringCaramia M, Dell\Paolo Dell'Olmo

ColoringCaramia M, Dell\Deliberazioni dell’ufficio di presidenza dell’assemblea legislativa regionale

ColoringCaramia M, Dell\Heuristics

ColoringCaramia M, Dell\An Examination of Expert Historian Heuristics Used by Secondary Students Engaged in the Analysis of Computer-enhanced Documents Relating to Women in the Early

ColoringCaramia M, Dell\2- "Corporate hedging and risk management theory: evidence from Polish listed companies", Author(s): Karol Marek Klimczak, Journal: The Journal of Risk Finance, Year: 2008 Volume: 9 Issue: 1 Page: 20 – 39

ColoringCaramia M, Dell\Verifica dell’apprendimento

ColoringCaramia M, Dell\Dell'economia e delle finanze

ColoringCaramia M, Dell\Per le energie rinnovabili dell’Italia

ColoringCaramia M, Dell\Об интеграции информационных ресурсов и создании научных электронных библиотек
Электронной библиотеки Республики Татарстан (РТ), а также издания таких международных электронных научных журналов, как “Lobachevskii...
ColoringCaramia M, Dell\La Facoltà di Economia dell’Università di Pavia 6

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница