A Polynomial Algorithm for the Degree-Constrained Minimum K-Tree Problem

Marshall L. Fisher
Additional contact information
Marshall L. Fisher: University of Pennsylvania, Philadelphia, Pennsylvania

Operations Research, 1994, vol. 42, issue 4, 775-779

Abstract: Given a graph with n + 1 nodes, a K -tree is defined to be a set of n + K edges that span the graph. This paper presents an algorithm for finding a minimum cost K -tree with a specified degree at a designated node. The algorithm runs in O ( n 3 ) time and is useful in the optimal solution of certain Lagrangian relaxations arising in vehicle routing.

Keywords: networks/graphs; tree algorithms: minimum k-tree algorithms; transportation; vehicle routing: optimization algorithm (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.4.775 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:4:p:775-779

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().