Publications related to Minimum spanning tree

Laser-Induced Graphene on Chitosan: An Enabling Technology for Sustainable Resistive Humidity Sensors

The development and characterization of resistive humidity sensors based on Chitosan on a glass substrate is reported. The sensor electrodes are made of laser-induced graphene derived from Chitosan, which represents a sustainability advancement by eliminat ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2023

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Mikhail Kapralov, Jakab Tardos

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on ...

IEEE COMPUTER SOC2022

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Adam Teodor Polak, Alexandra Anna Lassota

We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...

Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022

Scaling theory for the statistics of slip at frictional interfaces

Matthieu Wyart, Thomas Willem Jan de Geus

Slip at a frictional interface occurs via intermittent events. Understanding how these events are nucleated, can propagate, or stop spontaneously remains a challenge, central to earthquake science and tribology. In the absence of disorder, rate-and-state a ...

AMER PHYSICAL SOC2022

fGOT: Graph Distances Based on Filters and Optimal Transport

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic, Giovanni Chierchia

Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph dis ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2022

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

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

Uniform parsing for hyperedge replacement grammars

Petter Harald Ericson

It is well known that hyperedge-replacement grammars can generate NP-complete graph languages even under seemingly harsh restrictions. This means that the parsing problem is difficult even in the non-uniform setting, in which the grammar is considered to b ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2021

Tree in Tree: from Decision trees to Decision Graphs

Mahsa Shoaran, Bingzhao Zhu

Decision trees have been widely used as classifiers in many machine learning applications thanks to their lightweight and interpretable decision process. This paper introduces Tree in Tree decision graph (TnT), a framework that extends the conventional dec ...

Curran Associates, Inc, (NIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems)2021

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

Minimum spanning tree

Graph Chatbot

Chat with Graph Search

Laser-Induced Graphene on Chitosan: An Enabling Technology for Sustainable Resistive Humidity Sensors

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Scaling theory for the statistics of slip at frictional interfaces

fGOT: Graph Distances Based on Filters and Optimal Transport

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

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

Uniform parsing for hyperedge replacement grammars

Tree in Tree: from Decision trees to Decision Graphs

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

fGOT: Graph Distances Based on Filters and Optimal Transport

Spectral Hypergraph Sparsifiers of Nearly Linear Size

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

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

Laser-Induced Graphene on Chitosan: An Enabling Technology for Sustainable Resistive Humidity Sensors

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Uniform parsing for hyperedge replacement grammars

Scaling theory for the statistics of slip at frictional interfaces

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

Tree in Tree: from Decision trees to Decision Graphs