Minimum spanning tree

Formal sciences
Mathematics
Discrete mathematics
Graph theory

About
Privacy
Disclaimer

Graph Chatbot

Related publications (28)

Non-Exponential Variations for Classical Results in First Passage Percolation

Jacques Saliba

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges. We start by describing the asymptotic behavior of the diameter and the f ...

EPFL2020

Exceptional graphs for the random walk

Juhan Aru

If W is the simple random walk on the square lattice Z(2), then W induces a random walk W-G on any spanning subgraph G subset of Z(2) of the lattice as follows: viewing W as a uniformly random infinite word on the alphabet {x, -x, y, -y}, the walk W-G star ...

INST MATHEMATICAL STATISTICS2020

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

Benchmark for Bimanual Robotic Manipulation of Semi-deformable Objects

Aude Billard, Kunpeng Yao, Bernardo Fichera, Farshad Khadivar, Konstantinos Chatzilygeroudis, Ilaria Lauzana, Fanjun Bu

We propose a new benchmarking protocol to evaluate algorithms for bimanual robotic manipulation semi-deformable objects. The benchmark is inspired from two real-world applications: (a) watchmaking craftsmanship, and (b) belt assembly in automobile engines. ...

2020

Ramsey numbers of ordered graphs

Jan Kyncl

An ordered graph is a pair G = (G,

ELECTRONIC JOURNAL OF COMBINATORICS2020

Workflows in AiiDA: Engineering a high-throughput, event-based engine for robust and modular computational workflows

Nicola Marzari, Giovanni Pizzi, Martin Uhrin, Sebastiaan Philippe Huber

Over the last two decades, the field of computational science has seen a dramatic shift towards incorporating high-throughput computation and big-data analysis as fundamental pillars of the scientific discovery process. This has necessitated the developmen ...

2020

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

Christoph Hunkenschröder

We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approxi ...

2019

Finding a Needle in the Haystack of Hardened Interconnect Patterns

Paolo Ienne, Grace Zgheib, Stefan Nikolic

Circuits naturally exhibit recurring patterns of local interconnect. Hardening those patterns when designing Field Programmable Gate Array (FPGA) clusters can both eliminate slow programmable connections from the critical path and remove the need for trans ...

IEEE2019

Page 2 of 2