Personne

Tinaz Ekim

Cette personne n’est plus à l’EPFL

Publications associées (11)

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.

Connectez-vous pour utiliser Chat avec Graph Search

Split-critical and uniquely split-colorable graphs

Dominique de Werra, Bernard Ries, Tinaz Ekim

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 p ...

2010

A tutorial on the use of graph coloring for some problems in robotics

Dominique de Werra, Tinaz Ekim

We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the loc ...

2009

Partitioning graphs into complete and empty graphs

Tinaz Ekim

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j + k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j, k)-graph. For a fixed j and k ...

2009

Polarity of chordal graphs

Dominique de Werra, Tinaz Ekim

Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, th ...

2008

Polar cographs

Dominique de Werra, Tinaz Ekim

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 ...

Elsevier2008

Construction of balanced sports schedules using partitions into subleagues

Dominique de Werra, Tinaz Ekim

Direct constructions for balanced tournaments known so far solve problems with 2n teams if 2n mod 3 not equal 1 or 2n = 2(p), p >= 3 or n is odd. Our construction uses an arbitrary partition of the league into subleagues. It solves more than half of the mi ...

2008

Generalized vertex coloring problems using split graphs

Tinaz Ekim

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. ...

EPFL2006

Variations of split-coloring in permutation graphs

Dominique de Werra, Tinaz Ekim

Combinatorial optimization problems related to permutations have been widely studied. Here, we consider different generalizations of the usual coloring problem in permutation graphs. A cocoloring is a partition of a permutation into increasing and decreasi ...

2006

Precoloring with cliques and stable sets in cographs

Tinaz Ekim

Precoloring extension problems are known to be NP-complete in several classes of graphs. Here, we consider precolorings of cographs with not only stable sets but also with cliques. We give polynomial time algorithms to extend such a precoloring in an optim ...

2006

Partitioning cographs into cliques and stable sets

Dominique de Werra, Tinaz Ekim

We consider the problem of partitioning the node set of a graph into p cliques and k stable sets, namely the (p,k)-coloring problem. Results have been obtained for general graphs \cite{hellcomp}, chordal graphs \cite{hellchordal} and cacti for the case whe ...

2005