Publication

SAT-based Exact Modulo Scheduling Mapping for Resource-Constrained CGRAs

Related publications (34)

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.

Degree-constrained edge partitioning in graphs arising from discrete tomography

Dominique de Werra, Bernard Ries

Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k=3 colors is open. Variations and special ...

2009

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

On a graph coloring problem arising from discrete tomography

Dominique de Werra, Bernard Ries

An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph

G=(V,E)

and a family

\mathcal{P}

of chains

P_i

together with vectors

h(P_i)=(h_{i}^{1},...,h_{i}^{k})

, one wants to find a partition $V^{1},. ...

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

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

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

EPFL2007

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

(k,lambda)-colorings and universal graphs

Ivo Blöchliger, Daniela Bronner

We consider vertex k-colorings of an arbitrary simple, connected, and undirected graph G=(V,E) such that, for every vertex v, at most lambda different colors occur in the closed neighborhood of v. These colorings are called (k,lambda)-colorings. If a graph ...

2006

Fault-tolerant dynamic parallel schedules

Sebastian Gerlach

Dynamic Parallel Schedules (DPS) is a high-level framework for developing parallel applications on distributed memory computers such as clusters of PCs. DPS applications are defined by using directed acyclic flow graphs composed of user-defined operations. ...

EPFL2006

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

Suboptimal colorings and solution of large chromatic scheduling problems

Ivo Blöchliger

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

EPFL2005

On a graph coloring problem arising from discrete tomography

Dominique de Werra, Bernard Ries

An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph

G=(V,E)

and a family

\mathcal{P}

of chains

P_i

together with vectors

h(P_i)=(h_{i}^{1},...,h_{i}^{k})

, one wants to find a partition $V^{1},. ...

2008