2008/01/15 by V. A. Buslov, Buslov, V. A., V. A. Khudobakhshov +1
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Vehicle Routing Optimization Methods #cs.DM
paper · pdf · doi:10.48550/arxiv.0801.2347
3 pages
arxiv created 2008/01/15 · openalex publication_date 2008/01/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In general the problem of finding a miminum spanning tree for a weighted directed graph is difficult but solvable. There are a lot of differences between problems for directed and undirected graphs, therefore the algorithms for undirected graphs cannot usually be applied to the directed case. In this paper we examine the kind of weights such that the problems are equivalent and a minimum spanning tree of a directed graph may be found by a simple algorithm for an undirected graph.