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.
This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothernnic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718-7291. This paper pr ...
We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...
Starting from the famous Konigsberg bridge problem which Euler described in 1736, we intend to show that some results obtained 180 years later by Konig are very close to Euler's discoveries. ...
Starting from the basic image reconstruction problem in discrete tomography some graph theoretical models are proposed. This suggests the study of some variations and extensions of the basic problem. Applications in scheduling and timetabling are described ...
This paper addresses a multiprocessor generalization of the preemptive open-shop scheduling problem. The set of processors is partitioned into two groups and the operations of the jobs may require either single processors in either group or simultaneously ...
We consider the complexity of approximation for the INDEPENDENT DOMINATING SET problem in 2P(3)-free graphs, i.e., graphs that do not contain two disjoint copies of the chordless path on three vertices as all induced subgraph. We show that, if P not equal ...
We analyse the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin de ...
A magnet is a pair u, v of adjacent vertices such that the proper neighbours of u are completely linked to the proper neighbours of v. It has been shown that one can reduce the graph by removing the two vertices u, v of a magnet and introducing a new verte ...
An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G=(V,E) and a family P of chains Pi together with vectors h(Pi)=(hi1,...,hik), one wants to find a partition $V^{1},. ...
