An optimization problem on graphs
From MaRDI portal
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.
Recommendations
Cited in
(14)- Interval-parameter optimization problems on graphs
- Approximations for subset interconnection designs
- On complexity of subset interconnection designs
- On the minimum feasible graph for four sets
- Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
- scientific article; zbMATH DE number 4179413 (Why is no real title available?)
- scientific article; zbMATH DE number 4137790 (Why is no real title available?)
- scientific article; zbMATH DE number 3910419 (Why is no real title available?)
- A computational study of reduction techniques for the minimum connectivity inference problem
- Graphical method to solve combinatorial optimization problems
- An improved flow-based formulation and reduction principles for the minimum connectivity inference problem
- Some graph optimization problems with weights satisfying linear constraints
- Placing green bridges optimally, with a multivariate analysis
- A fast algorithm for computing a planar support for non-piercing rectangles
This page was built for publication: An optimization problem on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085182)
