An exact method to generate all nondominated spanning trees

DOI10.1051/RO/2016060MaRDI QIDQ2954355zbMATH OpenOpenAlexFDO

Authors Asma Boumesbah, Mohamed El-Amine Chergui

Publication date 12 January 2017

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ro/2016060

zbMATH Keywords

combinatorial optimizationminimum spanning treeinteger linear programmingbranch and bound methodmultiple objective linear optimization

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Combinatorial optimization (90C27) Integer programming (90C10)

Recommendations

• A flexible algorithm for generating all the spanning trees in undirected graphs
• scientific article; zbMATH DE number 177570
• An algorithm to generate all spanning trees with flow
• An almost-linear time algorithm for uniform random spanning tree generation
• scientific article; zbMATH DE number 1160278
• Divide-and-conquer based all spanning tree generation algorithm of a simple connected graph
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• Spanning trees with nonseparating paths
• An iteration method for computing the total number of spanning trees and its applications in graph theory
• Generating the maximum spanning trees of a weighted graph

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 4085440 (Why is no real title available?)
• scientific article; zbMATH DE number 3358495 (Why is no real title available?)
• A bicriterion shortest path algorithm
• A multiobjective branch-and-bound framework: application to the biobjective spanning tree problem
• Computing all efficient solutions of the biobjective minimum spanning tree problem
• Efficient cuts for generating the non-dominated vectors for Multiple Objective Integer Linear Programming
• Efficient spanning trees
• Multi-objective integer programming: a general approach for generating all non-dominated solutions
• Multi-objective integer programming: an improved recursive algorithm
• On spanning tree problems with multiple objectives
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Variable neighborhood search

Cited in

(2)

• On the enumeration of non-dominated spanning trees with imprecise weights
• Efficient generation of all regular non-dominated coteries

This page was built for publication: An exact method to generate all nondominated spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954355)