An Algorithm for Finding K Minimum Spanning Trees
From MaRDI portal
Publication:3906437
DOI10.1137/0210017zbMath0456.68075OpenAlexW2009938762MaRDI QIDQ3906437
Naoki Katoh, Toshihide Ibaraki, Hisashi Mine
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210017
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (23)
Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach ⋮ On spanning tree problems with multiple objectives ⋮ Finding the k smallest spanning trees ⋮ Computing all efficient solutions of the biobjective minimum spanning tree problem ⋮ An algorithm for \(k^{\text{th}}\) minimum spanning tree ⋮ The Kth TSP is pseudopolynomial when TSP is polynomial ⋮ Weighting factor extensions for finite multiple objective vector minimization problems ⋮ On the bicriterion - minimal cost/minimal label - spanning tree problem ⋮ Choquet-based optimisation in multiobjective shortest path and spanning tree problems ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ Enumerating \(K\) best paths in length order in DAGs ⋮ The saga of minimum spanning trees ⋮ Finding the \(k\) smallest spanning trees ⋮ Multicriteria path and tree problems: discussion on exact algorithms and applications ⋮ Enumerating the \(k\) best plane spanning trees ⋮ Exact algorithms for OWA-optimization in multiobjective spanning tree problems ⋮ A partial correlation vine based approach for modeling and forecasting multivariate volatility time-series ⋮ TAN classifiers based on decomposable distributions ⋮ On the \(K\) shortest path trees problem ⋮ Two-best solutions under distance constraints: The model and exemplary results for matroids ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Some basic exchange properties in combinatorial optimization and their application to constructing the k-best solutions ⋮ A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs
This page was built for publication: An Algorithm for Finding K Minimum Spanning Trees
