Skip to main navigation Skip to search Skip to main content

On the minimum feasible graph for four sets

  • CAS - Institute of Applied Mathematics
  • Xi'an Jiaotong University

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

Given a complete graph with vertex set X and subsets X 1, X 2,..., X n, the problem of finding a subgraph G with minimum number of edges such that for every i=1,2,..., n, G contains a spanning tree on X i, arises in the design of vacuum systems. In general, this problem is NP-complete and it is proved that for n=2 and 3 this problem is polynomial-time solvable. In this paper, we prove that for n=4, the problem is also polynomial-time solvable and give a method to construct the corresponding graph.

Original languageEnglish
Pages (from-to)457-462
Number of pages6
JournalApplied Mathematics
Volume10
Issue number4
DOIs
StatePublished - Dec 1995

Keywords

  • 1991 MR Subject Classification: 05A05
  • Feasible graph
  • NP-complete
  • heuristic
  • spanning tree

Fingerprint

Dive into the research topics of 'On the minimum feasible graph for four sets'. Together they form a unique fingerprint.

Cite this