Publications related to Graph coloring

Distributed Dynamics on Networks and their Applications in Network Communities, Sensor Networks and EEG's

Coupled neural networks, the Internet, World Wide Web, social networks and interacting biological networks are few examples of systems which consist of a large number of interacting dynamical units. Collective behavior of such systems is a consequence of t ...

EPFL2011

A Variational Framework for Structure from Motion in Omnidirectional Image Sequences

Pascal Frossard, Pierre Vandergheynst, Luigi Bagnato

We address the problem of depth and ego-motion estimation from omnidirectional images. We propose a correspondence-free structure from motion problem for images mapped on the 2-sphere. A novel graph-based variational framework is proposed for depth estimat ...

Springer Verlag2011

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

Shakhar Smorodinsky

Given a geometric hypergraph (or a range-space)

H=(V,\cal E)

, a coloring of its vertices is said to be conflict-free if for every hyperedge

S \in \cal E

there is at least one vertex in

S

whose color is distinct from the colors of all other vertices i ...

2010

On the power of combinatorial and spectral invariants

We extend the traditional spectral invariants (spectrum and angles) by a stronger polynomial time computable graph invariant based on the angles between projections of standard basis vectors into the eigenspaces (in addition to the usual angles between sta ...

2010

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

An optimal linear-time algorithm for interprocedural register allocation in high level synthesis is presented. Historically, register allocation has been modeled as a graph coloring problem, which is nondeterministic polynomial time-complete in general; ho ...

2010

Coloring axis-parallel rectangles

János Pach, Gábor Tardos

For every k and r, we construct a finite family of axis-parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r = 2, th ...

2010

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

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

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for thi ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

MARGIN: Maximal frequent subgraph mining

Ramachandra Satyanarayana Valluri

The exponential number of possible subgraphs makes the problem of frequent subgraph mining a challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs providing ample scope for pruning. MARGIN is a maximal su ...

2010

Graph coloring

Graph Chatbot

Chat with Graph Search

Distributed Dynamics on Networks and their Applications in Network Communities, Sensor Networks and EEG's

A Variational Framework for Structure from Motion in Omnidirectional Image Sequences

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

On the power of combinatorial and spectral invariants

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Coloring axis-parallel rectangles

Graph-based classification of multiple observation sets

Split-critical and uniquely split-colorable graphs

An Improved LP-based Approximation for Steiner Tree

MARGIN: Maximal frequent subgraph mining

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

On the power of combinatorial and spectral invariants

Coloring axis-parallel rectangles

MARGIN: Maximal frequent subgraph mining

Distributed Dynamics on Networks and their Applications in Network Communities, Sensor Networks and EEG's

A Variational Framework for Structure from Motion in Omnidirectional Image Sequences

Split-critical and uniquely split-colorable graphs

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Graph-based classification of multiple observation sets

An Improved LP-based Approximation for Steiner Tree