Publications associées à Graphe d'intervalles

Existence of dynamical low rank approximations for random semi-linear evolutionary equations on the maximal interval

An existence result is presented for the dynamical low rank (DLR) approximation for random semi-linear evolutionary equations. The DLR solution approximates the true solution at each time instant by a linear combination of products of deterministic and sto ...

2021

When Can Two Unlabeled Networks Be Aligned Under Partial Overlap?

Matthias Grossglauser, Ehsan Kazemi, Lyudmila Yartseva

Network alignment refers to the problem of matching the vertex sets of two unlabeled graphs, which can be viewed as a generalization of the classic graph isomorphism problem. Network alignment has applications in several fields, including social network an ...

2015

Coloring Relatives of Interval Overlap Graphs via On-line Games

Bartosz Maria Walczak

The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs defined by geometric representations and competitivity analysis of on-line algorithms. This connection became apparent after the recent construction ...

Springer-Verlag Berlin2014

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Bartosz Maria Walczak, Michal Lason

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line L if the intersection of any member with L is a nonempty segment. It is proved that the intersection graphs of simple families of com ...

Springer2014

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Bartosz Maria Walczak, Michal Lason

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the ...

Springer US2013

Coloring fuzzy circular interval graphs

Friedrich Eisenbrand, Martin Niemeier

Given a graph G with nonnegative node labels w, a multiset of stable sets S_1,...,S_k\subseteq V(G) such that each vertex v \in V(G) is contained in w(v) many of these stable sets is called a weighted coloring. The weighted coloring number \chi_w(G) is the ...

Elsevier2012

Coloring K-k-free intersection graphs of geometric objects in the plane

János Pach

The intersection graph of a collection C of sets is the graph on the vertex set C, in which C-1 . C-2 is an element of C are joined by an edge if and only if C-1 boolean AND C-2 not equal empty set. Erdos conjectured that the chromatic number of triangle-f ...

2012

Vision-Based Scene Understanding with Sparsity Promoting Priors

Alexandre Massoud Alahi

Human beings are interested in understanding their environments and the dynamic content that fills their surroundings. For applications ranging from security to marketing, people have installed networks of cameras to capture the dynamic elements of scenes. ...

EPFL2011

Network Design via Core Detouring for Problems Without a Core

Thomas Rothvoss

Some of the currently best-known approximation algorithms for network design are based on random sampling. One of the key steps of such algorithms is connecting a set of source nodes to a random subset of them. In a recent work [Eisenbrand,Grandoni,Rothvo\ ...

Springer2010

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

Evidence of time-dependent CP violation in the decay B^{0}→D^{+}D^{-}

Olivier Schneider, Aurelio Bay, Remi Léandre Albert Louvot, Chao Wang, Tagir Aushev, Vladislav Balagura, Jean Wicht, Nicolas Zwahlen, Jing Li

We report a measurement of the CP-odd fraction and the time-dependent CP violation in B-0 -> D*+D*- decays, using 657x10(6) BB events collected at the Upsilon(4S) resonance with the Belle detector at the KEKB asymmetric-energy e(+)e(-) collider. We measure ...

American Physical Society2009

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

Atrial repolarization as observable in the PQ interval

Zenichi Ihara

Objective: To study the involvement of atrial repolarization in body surface potentials. Methods: Electrocardiograms of healthy subjects were recorded using a 64-lead system. The data analysis focused on the PQ intervals, while devoting special attention t ...

2006

On the stable set polytope of claw-free graphs

Gautier Stauffer

In this thesis we focus our attention on the stable set polytope of claw-free graphs. This problem has been open for many years and albeit all the efforts engaged during those last three years, it is still open. This does not mean that no progress has been ...

EPFL2005

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

Measurement of the time-dependent CP-violating asymmetry in BO→KSOπOγ decays

Aurelio Bay, Stewart Cole, Tagir Aushev, Sun Hee Kim, Sanjeev Kumar, Jing Li

We present a new measurement of CP-violation parameters in B0→KS0π0γ decay based on a sample of 275×106 BB̄ pairs collected at the Υ(4S) resonance with the Belle detector at the KEKB energy-asymmetric e+e- collider. One of the B mesons is fully reconstruct ...

2005