Concept

Perfect graph

Related publications (96)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Graph-based classification of multiple observation sets

Pascal Frossard, Effrosyni Kokiopoulou

We consider the problem of classification of multiple observations of the same object, possibly under different transformations. We view this problem as a special case of semi-supervised learning where all unlabelled examples belong to the same unknown cla ...

Elsevier2010

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

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Dominique de Werra

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

2009

Optical Flow and Depth from Motion for Omnidirectional Images using a TV-L1 Variational Framework on Graphs

Pascal Frossard, Pierre Vandergheynst, Luigi Bagnato

This paper deals with the problem of efficiently computing the optical flow of image sequences acquired by omnidirectional (nearly full field of view) cameras. We formulate the problem in the natural spherical geometry associated with these devices and ext ...

2009

Graph transformations preserving the stability number

Dominique de Werra

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

2009

Coloring Fuzzy Circular Interval Graphs

Friedrich Eisenbrand, Martin Niemeier

Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs ...

Elsevier2009

A note on the data-driven capacity of P2P networks

Pascal Frossard

We consider two capacity problems in P2P networks. In the first one, the nodes have an infinite amount of data to send and the goal is to optimally allocate their uplink bandwidths such that the demands of every peer in terms of receiving data rate are met ...

2009

Preserving Privacy in Collaborative Filtering through Distributed Aggregation of Offline Profiles

Jean-Pierre Hubaux, Reza Shokri, Georgios Theodorakopoulos, Pedram Pedarsani

In recommender systems, usually, a central server needs to have access to users' profiles in order to generate useful recommendations. Having this access, however, undermines the users' privacy. The more information is revealed to the server on the user-it ...

ACM2009

Some coloring and walking problems in graphs

Benjamin Leroy-Beaulieu

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

EPFL2008

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