Finding Perfect Matchings in Bipartite Hypergraphs

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (32)

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

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

Discovering Influencers in Opinion Formation Over Social Graphs

Ali H. Sayed, Mert Kayaalp, Valentina Shumovskaia, Mert Cemri

The adaptive social learning paradigm helps model how networked agents are able to form opinions on a state of nature and track its drifts in a changing environment. In this framework, the agents repeatedly update their beliefs based on private observation ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2023

Privatized graph federated learning

Ali H. Sayed, Stefan Vlaski, Elsa Rizk

Federated learning is a semi-distributed algorithm, where a server communicates with multiple dispersed clients to learn a global model. The federated architecture is not robust and is sensitive to communication and computational overloads due to its one-m ...

SPRINGER2023

Metastability of the Potts Ferromagnet on Random Regular Graphs

Jean Bernoulli Ravelomanana

We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis ...

SPRINGER2023

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Akash Kumar

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

IEEE COMPUTER SOC2022

SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators

Nathanaël Perraudin, Andreas Loukas, Karolis Martinkus

We approach the graph generation problem from a spectral perspective by first generating the dominant parts of the graph Laplacian spectrum and then building a graph matching these eigenvalues and eigenvectors. Spectral conditioning allows for direct model ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2022

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...

EPFL2022

Nature vs. Nurture: Feature vs. Structure for Graph Neural Networks

Karl Aberer, Quoc Viet Hung Nguyen, Thành Tâm Nguyên, Chi Thang Duong

Graph neural networks take node features and graph structure as input to build representations for nodes and graphs. While there are a lot of focus on GNN models, understanding the impact of node features and graph structure to GNN performance has received ...

ELSEVIER2022

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Negar Kiyavash, Ehsan Mokhtarian, Saber Salehkaleybar

We study experiment design for unique identification of the causal graph of a system where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skele ...

2023

Page 3 sur 4