Digraphs of potential barriers: properties of their tree structure and algorithm for constructing minimum spanning forests

2025/04/20 by Buslov, Vasily · 1 citation
#05C20 (Primary) 05C35 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.2504.14484

Abstract

For a weighted digraph without loops V, the arc weights of which can be obtained from an undirected graph with loops \sf P according to the rule v_ij=p_ij-p_ii, the properties are studied. An effective algorithm for constructing directed trees of minimum weight and an algorithm for constructing spanning directed forests of minimum weight are proposed.

Cited by

• Splitting a graph by a given partition of the set of vertices based on the minimum weight of the induced trees

Related

• On the Minimum Spanning Tree for Directed Graphs with Potential Weights
• Algorithm for Constructing Related Spanning Directed Forests of Minimum Weight
• Counting two-forests and random cut size via potential theory
• Splitting a graph by a given partition of the set of vertices based on the minimum weight of the induced trees
• FPT algorithms for packing k-safe spanning rooted sub(di)graphs