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 language | English |
|---|---|
| Pages (from-to) | 457-462 |
| Number of pages | 6 |
| Journal | Applied Mathematics |
| Volume | 10 |
| Issue number | 4 |
| DOIs | |
| State | Published - 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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver