27 results on '"Werra, Dominique de"'
Search Results
2. What is my objective function?
- Author
-
Werra, Dominique de
- Subjects
Operations research -- Speeches, lectures and essays ,Business ,Business, general ,Business, international - Abstract
Dominique de Werra expressed both surprise and joy upon receiving the EURO XIV Gold Medal. Being a former EURO president, de Werra did not even expect to be one of the nominees. De Werra thanked his family, his colleagues and the EURO board, and also described operations research as a pure science, an open science, a natural science and an art. He concluded that OR is a basic science and the best education to modeling, and that it requires interdisciplinarity to become more successful.
- Published
- 1997
3. A partial view of OR in Switzerland
- Author
-
Werra, Dominique de and Hertz, Alain
- Subjects
Operations research -- Practice ,Business ,Business, general ,Business, international - Abstract
Operations research (OR) activities are alive and strong in Switzerland. The Assn. Suisse de Recherche Operationelle has a membership of 267 in addition to the 6,985,135 non-members who practice OR. In addition, the ten universities and two institutes of technology offer OR courses and carry out OR in cooperation with industries. At present, their work is concentrated on the areas of distribution, production, logistics, chemistry and scheduling.
- Published
- 1995
4. Résolution de problèmes d'horaire par la théorie des graphes
- Author
-
Werra, Dominique de and Blanc, Charles
- Published
- 2005
- Full Text
- View/download PDF
5. Chromatic scheduling
- Author
-
Werra, Dominique de, primary and Hertz, Alain, additional
- Full Text
- View/download PDF
6. Jean-Claude Badoux aura 60 ans
- Author
-
Delamuraz, Jean-Pascal, Weibel, Jean-Pierre, and Werra, Dominique de
- Published
- 1995
- Full Text
- View/download PDF
7. The mathematics of Peter L. Hammer (1936-2006): graphs, optimization, and Boolean models.
- Author
-
Boros, Endre, Crama, Yves, Werra, Dominique de, Hansen, Pierre, and Maffray, Frédéric
- Subjects
MATHEMATICIANS ,MATHEMATICAL research ,BOOLEAN algebra ,MATHEMATICAL combinations ,GRAPH theory - Abstract
The article focuses on Rutgers Center for Operations Research (RUTCOR) director Peter L. Hammer and his contributions to several areas of mathematical research including Boolean models, combination optimization, and graph theory. Born in Timisoara, Romania on December 23, 1936, Hammer founded RUTCOR in 1983. Hammer's scientific contributions earned him awards such as the George Tzitzeica prize and the Euler Medal. Publications by Hammer are listed.
- Published
- 2011
- Full Text
- View/download PDF
8. Coloration de graphes : fondements et applications
- Author
-
Werra, Dominique de and Kobler, Daniel
- Abstract
The classical colouring models are well known thanks in large part to their applications to scheduling type problems; we describe the basic concepts of colourings together with a number of variations and generalisations arising from scheduling problems such as the creation of school schedules. Some exact and heuristic algorithms will be presented, and we will sketch solution methods based on tabu search to find approximate solutions to large problems. Finally we will also mention the use of colourings for creating schedules in sports leagues and for computer file transfer problems. This paper is an extended version of [37].
- Published
- 2003
9. Split-critical and uniquely split-colorable graphs.
- Author
-
Ekim, Tınaz, Ries, Bernard, and Werra, Dominique de
- Subjects
- *
GRAPH theory , *MATHEMATICS , *ALGEBRA , *COMBINATORICS , *TOPOLOGY - Abstract
The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as criticality and the uniqueness of the minimum split-coloring. We discuss some properties of split-critical and uniquely split-colorable graphs. We describe constructions of such graphs with some additional properties. We also study the effect of the addition and the removal of some edge sets on the value of the split-chromatic number. All these results are compared with their cochromatic counterparts. We conclude with several research directions on the topic. [ABSTRACT FROM AUTHOR]
- Published
- 2010
10. Extended Decomposition for Mixed Integer Programming to Solve a Workforce Scheduling and Routing Problem
- Author
-
Rodrigo Lankaites Pinheiro, Wasakorn Laesanklang, Haneen Algethami, Dario Landa-Silva, Werra, Dominique de, Parlier, Greg H., and Vitoriano, Begoña
- Subjects
Set (abstract data type) ,Flexibility (engineering) ,Workforce scheduling ,Mathematical optimization ,Computer science ,media_common.quotation_subject ,Genetic algorithm ,Quality (business) ,Decomposition method (constraint satisfaction) ,Routing (electronic design automation) ,Integer programming ,media_common - Abstract
We propose an approach based on mixed integer programming (MIP) with decomposition to solve a workforce scheduling and routing problem, in which a set of workers should be assigned to tasks that are distributed across different geographical locations. We present a mixed integer programming model that incorporates important real-world features of the problem such as defined geographical regions and flexibility in the workers? availability. We decompose the problem based on geographical areas. The quality of the overall solution is affected by the ordering in which the sub-problems are tackled. Hence, we investigate different ordering strategies to solve the sub-problems. We also use a procedure to have additional workforce from neighbouring regions and this helps to improve results in some instances. We also developed a genetic algorithm to compare the results produced by the decomposition methods. Our experimental results show that although the decomposition method does not always outperform the genetic algorithm, it finds high quality solutions in practical computational times using an exact optimization method.
- Published
- 2015
11. Generalized vertex coloring problems using split graphs
- Author
-
Ekim, Tinaz and Werra, Dominique de
- Subjects
Graphes polaires ,Cocoloring ,Cocoloration ,Coloration de sommets généralisée ,Generalized vertex coloring ,Split-coloring ,Approximation ,Polar graphs ,Coloration Scindée - Abstract
Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. For mathematicians, it is interesting for an additional reason: it is extremely hard to solve it in an efficient way. In this thesis, we introduce several problems generalizing the usual vertex coloring problem, and hence, extending its application domain. We say that a graph is (p, k)-colorable if its vertex set can be partitioned into p cliques and k stable sets. Then, for a given p (respectively k), one may ask the following questions: how to choose p cliques (respectively k stable sets) to be removed from the graph such that the number of stable sets (respectively cliques) partitioning the remaining vertices is minimized? These are called (p, k)-coloring problems. We also introduce Min Split-coloring which is, given a graph G, the problem of minimizing k such that G is (k, k)-colorable. Along the saine line, given a graph G, the objective of the problem Min Cocoloring is to minimize p + k such that G is (p, k)-colorable. All these problems, called together generalized coloring problems, are obviously at least as difficult as Min Coloring. The purpose of this dissertation is to study generalized coloring problems in nome restricted classes of graphs in order to bring a new insight on the relative difficulties of these problems. To this end, we detect in a more precise way the limits between NP-hard and polynomially solvable problems. Chapter 1 introduces generalized coloring problems by emphasizing nome preliminary results which will guide the questions to handle in the following chapters. Chapter 2 exposes the first clans of graphs, namely cacti, where Min Split-coloring is shown to be polynomially solvable. We also observe that generalized coloring problems can be polynomially solved in triangulated graphs. The main result of Chapter 3 is a new characterization of cographs: it is equivalent to say that G is a cograph, and to state that, for every subgraph G' ⊆ G, G' is (p, k)-colorable if and only if G' [V \ K] is (p – 1, k)-colorable, where K induces a maximum clique of G'. This result implies simple combinatorial algorithme to solve all generalized coloring problems; the one for Min Cocoloring improves the best time complexity known so far. In Chapter 4, we handle the recognition of polar graphs which can be seen as a particular (p, k)-coloring, where p cliques are independent (i.e., not linked at all) and k stable sets form a complete k-partite graph. It is known that the recognition of polar graphs is NP-complete. Here, we determine the first clans of graphs, namely cographs, where the polar graphs can be recognized in polynomial time, more precisely in time O(n log n). We also give a characterization by forbidden subgraphs. In the came manner, we characterize monopolar cographs, i.e., cographs admitting a polar partition with at most one clique or at most one stable set. Chapter 5 is devoted to generalized coloring problems in line graphs. Here, we detect the first classes of graphs, namely line graphs of trees, line graphs of bipartite graphs and line graphs of line-perfect graphs, where generalized coloring problems diverge in terms of NP-hardness. In Chapter 6 we study the approximability of generalized coloring problems in line graphs, in comparability graphs and in general graphs. We derive approximation algorithms with a performance guarantee using both the standard approximation ratio and the differential approximation ratio. We show that both Min Split-coloring and Min Cocoloring are at least as hard as Min Coloring to approximate from the standard approximation ratio point of view, whereas, they admit a polynomial time differential approximation scheme and Min Coloring only a constant differential approximation ratio. We also show that Min Cocoloring reduces to Min Split-coloring in all classes of graphs closed under addition of disjoint cliques and under join of a complete k-partite graph. In Chapter 7, we handle two different applications of Min Split-coloring in permutation graphs. They give birth to a new problem, called Min Threshold-coloring, that we study in the came spirit as the other generalized coloring problems. In the last chapter, we present several open questions arising from this thesis.
- Published
- 2006
- Full Text
- View/download PDF
12. Nouvelles approches mathématiques des problèmes de conception et de pilotage des ateliers flexibles
- Author
-
Solot, Philippe and Werra, Dominique de
- Published
- 2005
- Full Text
- View/download PDF
13. Suboptimal colorings and solution of large chromatic scheduling problems
- Author
-
Blöchliger, Ivo and Werra, Dominique de
- Abstract
Graph Coloring is a very active field of research in graph theory as well as in the domain of the design of efficient heuristics to solve problems which, due to their computational complexity, cannot be solved exactly (no guarantee that an optimal solution will be reported), see [Cul] for a list of over 450 references. The graph coloring problem involves coloring the vertices of a given graph in such a way that two adjacent vertices never share the same color. The goal is to find the smallest number of colors needed to color all vertices in a fashion that satisfies this requirement. This number is called chromatic number and is denoted by Χ. In the first chapter, we present our research on suboptimal colorings and graphs which can be colored in such a way that the number of different colors appearing on the closed neighborhood (a vertex plus its neighbors) of any vertex v is less than Χ. We call such graphs oligomatic. The most interesting result is the following: given a graph and a coloring using Χ + p colors, there exists a vertex v such that there are at least Χ different colors among all vertices which are at a distance of [p/2] + 1 or less from v. We also study the existence of oligomatic graphs in special classes. Additionally, we present results of research on universal graphs which are "generic" oligomatic graphs in the sense that most properties of oligomatic graphs can be analyzed by restricting ourselves to universal graphs. Chapters Two to Four deal with the development of heuristics for two types of graph coloring problems. The tabu search heuristic was a central focus of our research. A tabu search iteratively modifies a candidate solution (which becomes the new candidate solution) with the goal of improving it. In such a procedure it is forbidden (tabu) to undo a modification for a certain number iterations. This mechanism allows to escape from local minima. In Chapter Two, we propose general improvements for tabu search based on some new and simple mechanisms (called reactive tabu schemes) to adapt the tabu tenure (which corresponds to the number of iterations a modification stays tabu). We also introduce distance and similarity measures for graph coloring problems which are needed in iterative procedures such as those of the tabu search. In the third chapter, we present the PARTIALCOL heuristic for the graph coloring problem. This method obtains excellent results compared to other similar methods and is able to color the well known DIMACS [JT96] benchmark graph flat300_28_0 optimally with 28 colors. (The best colorings found to date by other researchers use at least 31 colors.) PARTIALCOL uses partial solutions in its search space, which is a little explored way of approaching the graph coloring problem. Most approaches either use colorings and try to minimize the number of colors, or they use improper colorings (having conflicts, i.e. adjacent vertices which may have the same color) and try to minimize the number of conflicts. In the final chapter, we present a weighted version of the graph coloring problem which has applications in batch scheduling and telecommunication problems. We present two different adaptations of tabu search to the weighted graph coloring problem and test several of the reactive tabu schemes presented in Chapter Two. Further, we devise an adaptive memory algorithm AMA inspired by genetic algorithms. A large set of benchmark graphs with different properties is presented. All benchmark graphs with known optima have been solved to optimality by AMA. A key element of this algorithm is its capacity to determine the number k of colors to be used. Most other graph coloring heuristics need this parameter to be supplied by the user. Considering the results obtained on various graphs, we are confident that the methods developed are very efficient.
- Published
- 2005
- Full Text
- View/download PDF
14. Méthodes d'optimisation combinatoire pour des problèmes de graphes
- Author
-
Dubois, Nicolas and Werra, Dominique de
- Published
- 2005
- Full Text
- View/download PDF
15. Optimisation convexe dans les réseaux avec applications au trafic routier et à l'énergie électrique
- Author
-
Pasche, Claude and Werra, Dominique de
- Published
- 2005
- Full Text
- View/download PDF
16. Heuristiken für kombinatorische Optimierung und semantische Bildinhaltserkennung mit Techniken der künstlichen Intelligenz
- Author
-
Rogger, Andreas and Werra, Dominique de
- Published
- 2005
- Full Text
- View/download PDF
17. Sur quelques problèmes combinatoires relatifs à l'ordonnancement
- Author
-
Cochand, Maurice and Werra, Dominique de
- Published
- 2005
- Full Text
- View/download PDF
18. Recherches itératives dirigées parallèles
- Author
-
Taillard, Eric Denis and Werra, Dominique de
19. Modèles mathématiques pour une gestion efficace des ateliers flexibles
- Author
-
Widmer, Marino and Werra, Dominique de
20. From finding maximum feasible subsystems of linear systems to feedforward neural network design
- Author
-
Amaldi, Edoardo and Werra, Dominique de
21. Variations of coloring problems related to scheduling and discrete tomography
- Author
-
Ries, Bernard and Werra, Dominique de
- Subjects
Bipartite graph ,Graphe biparti ,Graphe mixte ,Scheduling ,Discrete tomography ,Complexity ,Graph coloring ,Edge partitioning ,Tomographie discrète ,Coloration de graphes ,Mixed graph ,Ordonnancement ,Complexité ,Partitionnement d'arêtes ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different colors. This thesis deals with some variations of this basic coloring problem which are related to scheduling and discrete tomography. These problems may also be considered as partitioning problems. In Chapter 1 basic definitions of computational complexity and graph theory are presented. An introduction to graph coloring and discrete tomography is given. In the next chapter we discuss two coloring problems in mixed graphs (i.e., graphs having edges and arcs) arising from scheduling. In the first one (strong mixed graph coloring problem) we have to cope with disjunctive constraints (some pairs of jobs cannot be processed simultaneously) as well as with precedence constraints (some pairs of jobs must be executed in a given order). It is known that this problem is NP-complete in mixed bipartite graphs. In this thesis we strengthen this result by proving that for k = 3 colors the strong mixed graph coloring problem is NP-complete even if the mixed graph is planar bipartite with maximum degree 4 and each vertex incident to at least one arc has maximum degree 2 or if the mixed graph is bipartite and has maximum degree 3. Furthermore we show that the problem is polynomially solvable in partial p-trees, for fixed p, as well as in general graphs with k = 2 colors. We also give upper bounds on the strong mixed chromatic number or even its exact value for some classes of graphs. In the second problem (weak mixed graph coloring problem), we allow jobs linked by precedence constraints to be executed at the same time. We show that for k = 3 colors this problem is NP-complete in mixed planar bipartite graphs of maximum degree 4 as well as in mixed bipartite graphs of maximum degree 3. Again, for partial p-trees, p fixed, and for general graphs with k = 2 colors, we prove that the weak mixed graph coloring problem is polynomially solvable. We consider in Chapter 3 the problem of characterizing in an undirected graph G = (V, E) a minimum set R of edges for which maximum matchings M can be found with specific values of p = |M ∩ R|. We obtain partial results for some classes of graphs and show in particular that for odd cacti with triangles only and for forests one can determine in polynomial time whether there exists a minimum set R for which there are maximum matchings M such that p= |R ∩ M|, for p= 0,1, ..., ν(G). The remaining chapters deal with some coloring (or partitioning) problems related to the basic image reconstruction problem in discrete tomography. In Chapter 4 we consider a generalization of the vertex coloring problem associated with the basic image reconstruction problem. We are given an undirected graph and a family of chains covering its vertices. For each chain the number of occurrences of each color is given. We then want to find a coloring respecting these occurrences. We are interested in both, arbitrary and proper colorings and give complexity results. In particular we show that for arbitrary colorings the problem is NP-complete with two colors even if the graph is a tree of maximum degree 3. We also consider the edge coloring version of both problems. Again we present some complexity results. We consider in Chapter 5 some generalized neighborhoods instead of chains. For each vertex x we are given the number of occurrences of each color in its open neighborhood Nd(x) (resp. closed neighborhood Nd+(x)), representing the set of vertices which are at distance d from x (resp. at distance at most d from x). We are interested in arbitrary colorings as well as proper colorings. We present some complexity results and we show in particular that for d = 1 the problems are polynomially solvable in trees using a dynamic programming approach. For the open neighborhood and d = 2 we obtain a polynomial time algorithm for quatrees (i.e. trees where all internal vertices have degree at least 4). We also examine the bounded version of these problems, i.e., instead of the exact number of occurrences of each color we are given upper bounds on these occurrences. In particular we show that the problem for proper colorings is NP-complete in bipartite graphs of maximum degree 3 with four colors and each color appearing at most once in the neighborhood N(x) of each vertex x. This result implies that the L(1,1)-labelling problem is NP-complete in this class of graphs for four colors. Finally in Chapter 6 we consider the edge partitioning version of the basic image reconstruction problem, i.e., we have to partition the edge set of a complete bipartite graph into k subsets such that for each vertex there must be a given number of edges of each set of the partition incident to this vertex. For k = 3 the complexity status is still open. Here we present a new solvable case for k = 3. Then we examine some variations where the union of two subsets E1, E2 has to satisfy some additional constraints as for example it must form a tree or a collection of disjoint chains. In both cases we give necessary and sufficient conditions for a solution to exist. We also consider the case where we have a complete graph instead of a complete bipartite graph. We show that the edge partitioning problem in a complete graph is at least as difficult as in a complete bipartite graph. We also give necessary and sufficient conditions for a solution to exist if E1 ∪ E2 form a tree or if they form a Hamiltonian cycle in the case of a complete graph. Finally we examine for both, complete and complete bipartite graphs, the case where each one of the sets E1 and E2 is structured (two disjoint Hamiltonian chains, two edge disjoint cycles) and present necessary and sufficient conditions.
22. Le problème de la répartition proportionnelle
- Author
-
Leyvraz, Jean-Pierre and Werra, Dominique de
23. Feedforward boolean neural networks with discrete weights computational power and training
- Author
-
Mayoraz, Eddy and Werra, Dominique de
24. La coloration des sommets d'un graphe et son application à la confection d'horaires
- Author
-
Hertz, Alain and Werra, Dominique de
25. Some combinatorial optimization problems in graphs with applications in telecommunications and tomography
- Author
-
Schindl, David and Werra, Dominique de
- Subjects
MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
The common point between the different chapters of the present work is graph theory. We investigate some well known graph theory problems, and some which arise from more specific applications. In the first chapter, we deal with the maximum stable set problem, and provide some new graph classes, where it can be solved in polynomial time. Those classes are hereditary, i.e. characterized by a list of forbidden induced subgraphs. The algorithms proposed are purely combinatorial. The second chapter is devoted to the study of a problem linked to security purposes in mobile telecommunication networks. The particularity is that there is no central authority guaranteeing security, but it is actually managed by the users themselves. The network is modelled by an oriented graph, whose vertices represent the users, and whose arcs represent public key certificates. The problem is to associate to each vertex a subgraph with some requirements on the size of the subgraphs, the number of times a vertex is taken in a subgraph and the connectivity between any two users as they put their subgraphs together. Constructive heuristics are proposed, bounds on the optimal solution and a tabu search are described and tested. The third chapter is on the problem of reconstructing an image, given its projections in terms of the number of occurrences of each color in each row and each column. The case of two colors is known to be polynomially solvable, it is NP-complete with four or more colors, and the complexity status of the problem with three colors is open. An intermediate case between two and three colors is shown to be solvable in polynomial time. The last two chapters are about graph (vertex-)coloring. In the fourth, we prove a result which brings a large collection of NP-hard subcases, characterized by forbidden induced subgraphs. In the fifth chapter, we approach the problem with the use of linear programming. Links between different formulations are pointed out, and some families of facets are characterized. In the last section, we study a branch and bound algorithm, whose lower bounds are given by the optimal value of the linear relaxation of one of the exposed formulations. A preprocessing procedure is proposed and tested.
26. Elaboration de tournées de véhicules sous contraintes d'accessibilité
- Author
-
Semet, Frédéric Julien and Werra, Dominique de
27. Some coloring and walking problems in graphs
- Author
-
Leroy-Beaulieu, Benjamin and Werra, Dominique de
- Subjects
forests ,quasi-adjoint graphs ,permutation graphs ,graphes de comparabilité ,co-interval graphs ,trees ,arbres ,online clique covering ,graphes de permutations ,circuit hamiltonien ,forêts ,Hamiltonian circuit ,graphes de cointervalles ,split graphs ,graphes quasi-adjoints ,online coloring ,comparability graphs ,graphes de chevauchement d'intervalles ,interval graphs ,graphes d'intervalles ,graphes scindés ,coloration online ,overlap graphs ,MathematicsofComputing_DISCRETEMATHEMATICS ,couverture par cliques online - Abstract
Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit problem. Chapter 1 presents basic definitions of graph theory, such as graph coloring, graph coloring with color-classes of bounded size b, and Hamiltonian circuits and paths. We also present online algorithms and online coloring. Chapter 2 starts with some general remarks about online graph covering with sets of bounded sizes (such as online bounded coloring): we give a simple method for transforming an online covering algorithm into an online bounded covering algorithm, and to derive the performance ratio of the bounded algorithm from the performance ratio of the unbounded algorithm. As will be shown in later chapters, this method often leads to optimal results. Furthermore, some basic preliminary results on online graph covering with sets of bounded size are given: for every graph, the performance ratio is bounded above by 1/2 + b/2 and for b = 2, this bound is optimal. In the second part, online coloring of co-interval graphs is studied. Based on two industrial applications, two different versions of this problem are discussed. In the case where the intervals are presented in increasing order of their left ends, we show that the performance ratio is 1 in the unbounded case and 2 - 1/b in the bounded case. In the case where the intervals may be presented in any order, we show that the performance ratio is at most 3 in the bounded case. Chapter 3 deals with online coloring of permutation and comparability graphs. First, we give a tight analysis of the First-Fit algorithm on bipartite permutation graphs and we show that its performance ratio is O(√n), even for some simple presentation orders. For both classes of graphs, we show that the performance ratio is bounded above by (χ+1)/2 in the unbounded case and that the performance ratio of First-Fit is equal to 1/2 + b/2 in the bounded case. In the second part of this chapter, we study cocoloring of permutation graphs. We show that the performance ratio is n/4 + 1/2 and we give better bounds in some more restricted cocoloring problems. Chapter 4 deals with an application of online coloring: the online Track Assignment Problem. Depending on the assumptions that are made, the Track Assignment Problem can be reduced to coloring permutation or overlap graphs online. We show that when a permutation graph is presented on a latticial plane, from west to east, then the performance ratio is exactly 2 - (min{b,k})-1, where k is the best known upper bound on the bounded chromatic number. We also show that, when a permutation graph is presented on a latticial plan, starting from the origin and growing, simultaneously or not, towards west and east, then the performance ratio is exactly 2 - 1/χ. We also show that online coloring overlap graphs does not have a performance ratio bounded by a constant, even if the overlap graph is bipartite and presented in increasing order of the intervals left ends. In this special case, we show that First-Fit has a tight performance ratio of O(√n). We consider coloring overlap graphs online where the intervals have a bounded size between 1 and a given number M. In this case, we show that the performance ratio can be bounded above by 2√M if M ≤ M0, and by log M (⎡log M / log log M⎤ + 1) if M > M0, M0 being defined by the equation 2√M0 = 3 log(M0). For large values of M, the ratio is O(log2 M / log log M). Chapter 5 is about online coloring of trees, forests and split-graphs. For trees, we show that the performance ratio of online coloring is exactly ½log2(2n) in the unbouded case and at most 1 + ⎣log2(b)⎦/χb in the bounded case. For split-graphs, we show that the performance ratio of online coloring is exactly 1 + 1/χ in the unbounded case and is at most 2 + 1/χb + 3/b in the bounded case. In Chapter 6, we present a class of digraphs: the quasi-adjoint graphs. These are a super class of both the graphs used for a DNA sequencing algorithm in (Blazewicz, Kasprzak, "Computational complexity of isothermic DNA sequencing by hybridization", 2006) and the adjoints. A polynomial recognition algorithm in O(n3), as well as a polynomial algorithm in O(n2 + m2) for finding a Hamiltonian circuit in quasi-adjoint graphs are given. Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a sequence of two consecutive arcs) are discussed.
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.