Concept

Coloration fractionnaire

Publications associées (27)

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Ieee-Inst Electrical Electronics Engineers Inc2024

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

Lukas Fritz Felix Vogl

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

Differentially private multi-agent constraint optimization

Boi Faltings, Aleksei Triastcyn, Sankarshan Damle, Sujit Prakash Gujar

Distributed constraint optimization (DCOP) is a framework in which multiple agents with private constraints (or preferences) cooperate to achieve a common goal optimally. DCOPs are applicable in several multi-agent coordination/allocation problems, such as ...

Springer2024

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...

IEEE COMPUTER SOC2022

Differentially Private Multi-Agent Constraint Optimization

Boi Faltings, Sujit Prakash Gujar, Sankarshan Damle, Aleksei Triastcyn

Several optimization scenarios involve multiple agents that desire to protect the privacy of their preferences. There are distributed algorithms for constraint optimization that provide improved privacy protection through secure multiparty computation. How ...

ACM2022

From Boolean functions to quantum circuits: A scalable quantum compilation flow in C++

Giovanni De Micheli, Fereshte Mozafari Ghoraba, Heinz Riener, Giulia Meuli, Bruno Schmitt Antunes

We propose a flow for automated quantum compila- tion. Our flow takes a Boolean function implemented in Python as input and translates it into a format appropriate for reversible logic synthesis. We focus on two quantum compilation tasks: uniform state pre ...

2021

Edge colorings of graphs without monochromatic stars

Abhishek Methuku

In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an ...

Elsevier2020

Distributed Coloring of Graphs with an Optimal Number of Colors

Etienne Michel François Bamas

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

Stability results for vertex Turan problems in Kneser graphs

Abhishek Methuku

The vertex set of the Kneser graph K(n, k) is V = (([n])(k)) and two vertices are adjacent if the corresponding sets are disjoint. For any graph F, the largest size of a vertex set U subset of V such that K(n, k)[U] is F-free, was recently determined by Al ...

2019

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delt ...

IEEE COMPUTER SOC2019

Monochromatic cycle covers in random graphs

Dániel József Korándi

A classic result of Erdos, Gyarfas and Pyber states that for every coloring of the edges of K-n with r colors, there is a cover of its vertex set by at most f(r)=O(r2logr) vertex-disjoint monochromatic cycles. In particular, the minimum number of such cove ...

WILEY2018

Coordination of Dynamic Software Components with JavaBIP

Simon Bliudze, Anastasia Mavridou

JavaBIP allows the coordination of software components by clearly separating the functional and coordination aspects of the system behavior. JavaBIP implements the principles of the BIP component framework rooted in rigorous operational semantics. Recent w ...

Springer International Publishing2017

Unsplittable coverings in the plane

János Pach, Doemoetoer Palvoelgyi

A system of sets forms an m-fold covering of a set X if every point of X belongs to at least m of its members. A 1-fold covering is called a covering. The problem of splitting multiple coverings into several coverings was motivated by classical density est ...

Academic Press Inc Elsevier Science2016

Unsplittable Coverings in the Plane

János Pach, Doemoetoer Palvoelgyi

Springer-Verlag Berlin2016

On random subgraphs of Kneser and Schrijver graphs

Andrei Kupavskii

A Kneser graph KG(n,k) is a graph whose vertices are in oneto-one correspondence with k -element subsets of [n], with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lowisz states that the chromatic num ...

Academic Press Inc Elsevier Science2016

Induced Matchings In Graphs Of Degree At Most 4

Viet Hang Nguyen

For a graph G, let nu(s)(G) be the strong matching number of G. We prove the sharp bound nu(s)(G) >= n(G)/9 for every graph G of maximum degree at most 4 and without isolated vertices that does not contain a certain blown-up 5-cycle as a component. This re ...

SIAM Publications2016

The Erdos-Hajnal conjecture for rainbow triangles

János Pach

We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order ohm(n(1/3) log(2) n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjectu ...

Academic Press Inc Elsevier Science2015

Optimal pathway reconstruction on 3D NMR maps

Dominique de Werra

A three-dimensional Nuclear Magnetic Resonance (NMR) map displays the results of NMR experiments, that allow to determine the shape of a biological molecule. Shape calculation starts from a reconstruction of a sequence of NMR signals, which is equivalent t ...

Elsevier Science Bv2015

Triangle-free intersection graphs of line segments with large chromatic number

Bartosz Maria Walczak, Michal Lason

In the 1970s Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer k we construct a triangle-free fam ...

Academic Press Inc Elsevier Science2014

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