Publications associées à Graphe médian

Results on Sparse Integer Programming and Geometric Independent Sets

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

EPFL2023

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

Jana Tabea Cslovjecsek

We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...

Carleton Univ, Dept Mathematics & Statistics2023

Frequent asymmetric migrations suppress natural selection in spatially structured populations

Anne-Florence Raphaëlle Bitbol, Alia Abbara

Natural microbial populations often have complex spatial structures. This can impact their evolution, in particular the ability of mutants to take over. While mutant fixation probabilities are known to be unaffected by sufficiently symmetric structures, ev ...

Oxford Univ Press2023

A Topological characterisation of Weisfeiler-Leman equivalence classes

Graph Neural Networks (GNNs) are learning models aimed at processing graphs and signals on graphs. The most popular and successful GNNs are based on message passing schemes. Such schemes inherently have limited expressive power when it comes to distinguish ...

2022

Adaptive majority problems for restricted query graphs and for weighted sets

Abhishek Methuku, Balázs Keszegh, Doemoetoer Palvoelgyi

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

ELSEVIER2021

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

Balázs Keszegh, Abhishek Methuku, Doemoetoer Palvoelgyi

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

COMENIUS UNIV2019

On the Zarankiewicz problem for intersection hypergraphs

János Pach

Let d and t be fixed positive integers, and let denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem ...

Academic Press Inc Elsevier Science2016

Graph-based compression of dynamic 3D point cloud sequences

Pascal Frossard, Ntorina Thanou

This paper addresses the problem of compression of 3D point cloud sequences that are characterized by moving 3D positions and color attributes. As temporally successive point cloud frames are similar, motion estimation is key to effective compression of th ...

Institute of Electrical and Electronics Engineers2016

Enhancing synchronizability of dynamical networks using the connection graph stability method

Martin Hasler, Ali Ajdari Rad, Mahdi Jalili

Dynamical networks with diffusive couplings are investigated from the point of view of synchronizability. Arbitrary connection graphs are admitted but the coupling is symmetric. Networks with equal interaction coefficients for all edges of the interaction ...

2007