  We deal with algorithmic techniques for minimal cost input-connectivity while
maintaining controllability of linear systems. The input matrix is assumed to
be constrained in the sense that the set of states that each input (if present)
can influence is known a priori, and that each interconnection between an input
and a state is associated with a certain cost. In this setting we determine a
set of input-connections that lead to the minimum cost and ensures that the
resulting system is structurally controllable. We also identify a sparsest set
of input-connections with minimum cost while maintaining structural
controllability of the system. A large class of systems are identified for
which these problems are solvable in polynomial time using efficient
algorithms. A 2-approximation solution is presented for the general case.
Graph-theoretic tools are employed to tackle the above class of constrained
design problems. Illustrative examples are included to demonstrate the efficacy
of the techniques developed here.
