Publications related to Independence number of generalized Petersen graphs

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 ...

Oxford2023

Brain Fingerprinting Using Fmri Spectral Signatures On High-Resolution Cortical Graphs

Dimitri Nestor Alice Van De Ville, Maria Giulia Preti, Hamid Behjat, Stefano Moia, Carlo Ferritto

Resting-state fMRI has proven to entail subject-specific signatures that can serve as a fingerprint to identify individuals. Conventional methods are based on building a connectivity matrix based on correlation between the average time course of pairs of b ...

IEEE2023

Scalable maximal subgraph mining with backbone-preserving graph convolutions

Karl Aberer, Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên

Maximal subgraph mining is increasingly important in various domains, including bioinformatics, genomics, and chemistry, as it helps identify common characteristics among a set of graphs and enables their classification into different categories. Existing ...

ELSEVIER SCIENCE INC2023

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

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 ...

2022

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

On the robustness of the metric dimension of grid graphs to adding a single edge

Patrick Thiran, Gergely Odor, Satvik Mehul Mashkaria

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to t ...

2022

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

The power of adaptivity in source identification with time queries on the path

Patrick Thiran, Gergely Odor, Victor Cyril L Lecomte

We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph

G=(V,E)

, an unknown source node

v^* \in V

is drawn uniformly at random, ...

2022

Adaptive majority problems for restricted query graphs and for weighted sets

Abhishek Methuku, Balázs Keszegh

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

Independence number of generalized Petersen graphs

Graph Chatbot

Chat with Graph Search

Frequent asymmetric migrations suppress natural selection in spatially structured populations

Brain Fingerprinting Using Fmri Spectral Signatures On High-Resolution Cortical Graphs

Scalable maximal subgraph mining with backbone-preserving graph convolutions

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

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Space-Efficient Representations of Graphs

On the robustness of the metric dimension of grid graphs to adding a single edge

A Topological characterisation of Weisfeiler-Leman equivalence classes

The power of adaptivity in source identification with time queries on the path

Adaptive majority problems for restricted query graphs and for weighted sets

Frequent asymmetric migrations suppress natural selection in spatially structured populations

Scalable maximal subgraph mining with backbone-preserving graph convolutions

Brain Fingerprinting Using Fmri Spectral Signatures On High-Resolution Cortical Graphs

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

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Space-Efficient Representations of Graphs

On the robustness of the metric dimension of grid graphs to adding a single edge

The power of adaptivity in source identification with time queries on the path

A Topological characterisation of Weisfeiler-Leman equivalence classes

Adaptive majority problems for restricted query graphs and for weighted sets