Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Connectivity (graph theory)

Related publications (29)

Adaptive majority problems for restricted query graphs and for weighted sets

Doemoetoer Palvoelgyi, 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

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Adam Teodor Polak

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Learning Bollobas-Riordan Graphs Under Partial Observability

Ali H. Sayed

This work examines the problem of learning the topology of a network (graph learning) from the signals produced at a subset of the network nodes (partial observability). This challenging problem was recently tackled assuming that the topology is drawn acco ...

IEEE2021

Design and Simulation of a Wide-Bandwidth CMUTs Array with Dual-Mixed radii and Multi Operating Modes

Yu Bai, Yihe Zhao

A capacitive micromachined ultrasonic transducers (CMUTs) array with dual-mixed radii is designed to improve bandwidth and realize multi-modes operating for immersed ultrasonic applications. The two-size (TS) CMUT array is composed of two sub-arrays with d ...

IEEE2021

Connectivity Measures Differentiate Cortical and Subcortical Sub-Acute Ischemic Stroke Patients

Silvestro Micera

Brain lesions caused by cerebral ischemia lead to network disturbances in both hemispheres, causing a subsequent reorganization of functional connectivity both locally and remotely with respect to the injury. Quantitative electroencephalography (qEEG) meth ...

FRONTIERS MEDIA SA2021

Representation Learning for Multi-relational Data

Eda Bayram

Recent years have witnessed a rise in real-world data captured with rich structural information that can be better depicted by multi-relational or heterogeneous graphs. However, research on relational representation learning has so far mostly focused on th ...

EPFL2021

On the Capacity of Non-Coherent Network Coding

Christina Fragouli, Suhas Diggavi, Soheil Mohajerzefreh, Mahdi Jafari

The min-cut value towards a single receiver in a network with unit capacity edges can be achieved by routing a single bit. The multicast theorem in network coding shows that, the common min-cut value towards N >= 1 receivers can also be achieved using pack ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009

What graph neural networks cannot learn: depth vs width

Andreas Loukas

This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attribut ...

2020

Symbolic Algorithms for Token Swapping

Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...

2020

Related publications (29)