Concept

K-vertex-connected graph

Related publications (65)

BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

Siam Publications2024

Molecular hypergraph neural networks

Philippe Schwaller, Junwu Chen

Graph neural networks (GNNs) have demonstrated promising performance across various chemistry-related tasks. However, conventional graphs only model the pairwise connectivity in molecules, failing to adequately represent higher order connections, such as m ...

Aip Publishing2024

OpenPifPaf: Composite Fields for Semantic Keypoint Detection and Spatio-Temporal Association

Alexandre Massoud Alahi, Sven Kreiss, Lorenzo Bertoni

Many image-based perception tasks can be formulated as detecting, associating and tracking semantic keypoints, e.g., human body pose estimation and tracking. In this work, we present a general framework that jointly detects and forms spatio-temporal keypoi ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

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

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

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

Yu Bai, Zhengwen Jiang, Yihe Zhao, Jie Li, Zichen Liu

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

Learning Bollobas-Riordan Graphs Under Partial Observability

Ali H. Sayed, Michele Cirillo

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

Metric dimension of critical Galton–Watson trees and linear preferential attachment trees

Gergely Odor

The metric dimension of a graph G is the minimal size of a subset R of vertices of G that, upon reporting their graph distance from a distinguished (source) vertex v⋆, enable unique identification of the source vertex v⋆ among all possible vertices of G. I ...

2021

Efficient Distributed Transposition Of Large-Scale Multigraphs And High-Cardinality Sparse Matrices

Felix Schürmann, Bruno Ricardo Da Cunha Magalhães

Graph-based representations underlie a wide range of scientific problems. Graph connectivity is typically represented as a sparse matrix in the Compressed Sparse Row format. Large-scale graphs rely on distributed storage, allocating distinct subsets of row ...

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

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.