An optimization problem on graphs
type: Item
instance of: scholarly article
title: An optimization problem on graphs
zbMATH Open document ID: 0607.05047
DOI: 10.1016/0166-218X(86)90010-7
author: Du Ding-Zhu
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: A graph G with vertex set \(X=\cup^{n}_{i=1}X_ i\), for n given sets \(X_ i\), is called a feasible graph for \((X_ 1,...,X_ n)\) if, for each \(X_ i\), the subgraph \(G_ i\), with vertex set \(X_ i\), is connected. The authors consider the (NP-hard) problem of finding a minimum feasible graph. They give a sufficient condition, that can be checked in polynomial time, for a graph to be minimum. In addition, they show how every minimum feasible graph for \((X_ 1,...,X_ n)\) can be obtained from any such graph.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3981214
zbMATH Keywords: NP-completeness
zbMATH Keywords: minimum feasible graph
MaRDI profile type: Publication
cites work: Q4198056
description: scientific article; zbMATH DE number 3981214