Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
Graph Chatbot
Chattez avec Graph Search
Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.
AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.
A binary tanglegram is a pair (S, T) of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics, it is essential that both trees are drawn without edge ...
The interference graph for a procedure in Static Single Assignment (SSA) Form is chordal. Since the k-colorability problem can be solved in polynomial-time for chordal graphs, this result has generated interest in SSA-based heuristics for spilling and coal ...
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 ...
We are interested in coloring the edges of a mixed graph. i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds oil the number of requ ...
A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with in edges can be separated into two parts of roughly equal size by the removal of O(m(3/4)root log m) vertices. This result is then ...
We consider a gauge symmetric version of the p-spin glass model on a complete graph. The gauge symmetry guarantees the absence of replica symmetry breaking and allows to fully use the interpolation scheme of Guerra to rigorously compute the free energy. In ...
We consider the binary consensus problem where each node in the network initially observes one of two states and the goal for each node is to eventually decide which one of the two states was initially held by the majority of the nodes. Each node contacts ...
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009
Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s, k)-polar if there exists a partition A, B of its vertex set such that A induces a complete s-partite grap ...
Wireless sensor networks have emerged a few years ago, enabling large scale sensing at low cost. There are many interesting problems related to this new sensing tool: designing robust and small hardware, defining adapted routing protocols, minimizing the e ...
In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer ...
