A Study of the Facial Structure of a Class of Polytopes Related to the Steiner Tree Problem

Abstract

Given an undirected graph G = (N,A) with positive arc weights a subset of two or more nodes of N, the Steiner Tree problem on graphs (STG) is to find T, a connected subgraph of G such that all the nodes of P are included in T and the sum of the weights of the arcs in T is minimized. In the general case, STG is NP-hard. A method of attacking NP-hard combinatorial problems, which has not been generally exploited in the case of the Steiner tree problem, is that of polyhedral combinatorics. This method of attack revolves around studying the characteristics of the convex hull of feasible solutions. We define a class of polytopes related to the Steiner Tree problem on graphs and examine inequalities generated by placing connectivity requirements on these graphs. We define a class of facets induced by inequalities that specify the number of arcs which must flow across cuts and between the sets of a partition of the nodes.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1988
Accession Number
ADA217446

Entities

People

  • Keith A. Ware

Organizations

  • Air Force Institute of Technology

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computer Programming
  • Construction
  • Coverings
  • Equations
  • Hierarchies
  • Inequalities
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • New York
  • North Carolina
  • Notation
  • Operations Research
  • Students
  • Terminals

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research