Problem Statements for k-Node Shortest Path and k-Node Shortest Cycle in a Complete Graph

The author formulates mixed Boolean linear programming problems to find the shortest route and the shortest cycle that pass through the given number of nodes in a complete graph. Their special cases provide formulations of problems for finding the shortest Hamiltonian path and the shortest Hamiltoni...

Full description

Saved in:
Bibliographic Details
Published in:Cybernetics and systems analysis 2016, Vol.52 (1), p.71-75
Main Author: Stetsyuk, P. I.
Format: Article
Language:English
Subjects:
Artificial Intelligence
Control
Mathematics
Mathematics and Statistics
Processor Architectures
Software Engineering/Programming and Operating Systems
Systems Theory
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The author formulates mixed Boolean linear programming problems to find the shortest route and the shortest cycle that pass through the given number of nodes in a complete graph. Their special cases provide formulations of problems for finding the shortest Hamiltonian path and the shortest Hamiltonian cycle. The problems include no more than 2n 2 variables and no more than (n + 1) 2 constraints, where n is the number of nodes of the complete graph.
ISSN:1060-0396
1573-8337
DOI:10.1007/s10559-016-9801-x