The generalized minimum spanning tree polytope and related polytopes

P.C. Pop

Research output: Book/ReportReportOther research output

12 Downloads (Pure)

Abstract

The Generalized Minimum Spanning Tree problem denoted by GMST is a variant of the classical Minimum Spanning Tree problem in which nodes are partitioned into clusters and the problem calls for a minimum cost tree spanning at least one node from each cluster. A different version of the problem, called E-GMST arises when exactly one node from each cluster has to be visited. Both GMST problem and E-GMST problem are NP-hard problems. In this paper, we model GMST problem and E-GMST problem as integer linear programs and study the facial structure of the corresponding polytopes.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages9
Publication statusPublished - 2001

Publication series

NameMemorandum
PublisherDepartment of Applied Mathematics, University of Twente
No.1587
ISSN (Print)0169-2690

Fingerprint

Minimum Spanning Tree
Polytopes
Polytope
Vertex of a graph
Integer Program
NP-hard Problems
Spanning tree
Linear Program
Costs

Keywords

  • MSC-05C05
  • MSC-90C11
  • IR-65774
  • MSC-90B10
  • EWI-3407
  • MSC-90C27

Cite this

Pop, P. C. (2001). The generalized minimum spanning tree polytope and related polytopes. (Memorandum; No. 1587). Enschede: University of Twente, Department of Applied Mathematics.
Pop, P.C. / The generalized minimum spanning tree polytope and related polytopes. Enschede : University of Twente, Department of Applied Mathematics, 2001. 9 p. (Memorandum; 1587).
@book{c1c86df45c6f4447ac4e4a1aa1a10f95,
title = "The generalized minimum spanning tree polytope and related polytopes",
abstract = "The Generalized Minimum Spanning Tree problem denoted by GMST is a variant of the classical Minimum Spanning Tree problem in which nodes are partitioned into clusters and the problem calls for a minimum cost tree spanning at least one node from each cluster. A different version of the problem, called E-GMST arises when exactly one node from each cluster has to be visited. Both GMST problem and E-GMST problem are NP-hard problems. In this paper, we model GMST problem and E-GMST problem as integer linear programs and study the facial structure of the corresponding polytopes.",
keywords = "MSC-05C05, MSC-90C11, IR-65774, MSC-90B10, EWI-3407, MSC-90C27",
author = "P.C. Pop",
note = "Imported from MEMORANDA",
year = "2001",
language = "English",
series = "Memorandum",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1587",

}

Pop, PC 2001, The generalized minimum spanning tree polytope and related polytopes. Memorandum, no. 1587, University of Twente, Department of Applied Mathematics, Enschede.

The generalized minimum spanning tree polytope and related polytopes. / Pop, P.C.

Enschede : University of Twente, Department of Applied Mathematics, 2001. 9 p. (Memorandum; No. 1587).

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - The generalized minimum spanning tree polytope and related polytopes

AU - Pop, P.C.

N1 - Imported from MEMORANDA

PY - 2001

Y1 - 2001

N2 - The Generalized Minimum Spanning Tree problem denoted by GMST is a variant of the classical Minimum Spanning Tree problem in which nodes are partitioned into clusters and the problem calls for a minimum cost tree spanning at least one node from each cluster. A different version of the problem, called E-GMST arises when exactly one node from each cluster has to be visited. Both GMST problem and E-GMST problem are NP-hard problems. In this paper, we model GMST problem and E-GMST problem as integer linear programs and study the facial structure of the corresponding polytopes.

AB - The Generalized Minimum Spanning Tree problem denoted by GMST is a variant of the classical Minimum Spanning Tree problem in which nodes are partitioned into clusters and the problem calls for a minimum cost tree spanning at least one node from each cluster. A different version of the problem, called E-GMST arises when exactly one node from each cluster has to be visited. Both GMST problem and E-GMST problem are NP-hard problems. In this paper, we model GMST problem and E-GMST problem as integer linear programs and study the facial structure of the corresponding polytopes.

KW - MSC-05C05

KW - MSC-90C11

KW - IR-65774

KW - MSC-90B10

KW - EWI-3407

KW - MSC-90C27

M3 - Report

T3 - Memorandum

BT - The generalized minimum spanning tree polytope and related polytopes

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Pop PC. The generalized minimum spanning tree polytope and related polytopes. Enschede: University of Twente, Department of Applied Mathematics, 2001. 9 p. (Memorandum; 1587).