1

Structural cost-optimal design of sensor networks
for distributed estimation

arXiv:1804.01799v1 [cs.SY] 5 Apr 2018

Mohammadreza Doostmohammadian†∗ , Member, IEEE, Hamid R. Rabiee†, Senior Member, IEEE, Usman A.
Khan§ , Senior Member, IEEE

Abstract—In this letter we discuss cost optimization of sensor networks monitoring structurally full-rank systems under
distributed observability constraint. Using structured systems
theory, the problem is relaxed into two subproblems: (i) sensing
cost optimization and (ii) networking cost optimization. Both
problems are reformulated as combinatorial optimization problems. The sensing cost optimization is shown to have a polynomial
order solution. The networking cost optimization is shown to
be NP-hard in general, but has a polynomial order solution
under specific conditions. A 2-approximation polynomial order
relaxation is provided for general networking cost optimization,
which is applicable in large-scale system monitoring.
Index Terms – Distributed Estimation, System Digraph, Structural Observability, Combinatorics, Cost Optimization

I. I NTRODUCTION
Single time-scale distributed estimation among a group of
sensors/agents has been the topic of interest in the signalprocessing literature [1]–[11]. In this paper, it is assumed that
the underlying system is structurally full-rank (also known as
structurally cyclic systems), which is also the case in [12],
[13]. This is a typical assumption in distributed estimation
literature as in [4], [5], [9], [10], where proper sensor measurements (sensing) satisfying observability constraints along
with sufficient information sharing among sensors (networking) provide distributed estimation of system with bounded
error. The idea in this paper is to minimize the cost of
sensing and networking while satisfying distributed observability constraints. The related literature on this problem (with
observability constraint) is limited [12]–[14] and the problem
is to great extent unexplored. To solve the problem, structural
relaxations are applied to formulate the problem as proper
combinatorial optimization format, knowing that structural
relaxations are valid for almost all possible numerical values
of system parameters [15].
In this paper, optimization of sensing and networking
cost are considered. Note that state measurements by sensors have certain cost. The sensing cost is similar to cost
of sensor selection, and the networking cost is similar to
link/communication cost. The sensor measurement cost might
be due to, for example, sensor range/calibration, sensor’s
energy/power consumption, maintenance/embedding expenses
† ICT Innovation Center for Advanced Information and Communication Technology, Sharif University of Technology, Tehran, Iran
rabiee@sharif.edu.
∗ (corresponding author) Mechanical Engineering Department, Semnan
University, Semnan, Iran doost@profs.semnan.ac.ir.
§ Electrical and Computer Engineering Department, Tufts University,
Medford, USA khan@ece.tufts.edu.

for sensor placement, and even environmental condition such
as humidity/temperature. On the other hand, every link in
the sensor network has a cost, representing, for example,
data transmission energy, and communication cost of sensors
that may be subject to environmental conditions. As the
first contribution, we show that the sensing cost optimization
problem for structurally full-rank systems has a polynomial
order solution with complexity O(m3 ). This is a significant
result, as in [14] authors claim that for general systems there
is no polynomial-order solution for sensing cost optimization,
i.e. the problem is NP-hard1 . Another related literature, [16]
considers sensor selection for reducing the measurement error, while in [17] near-optimal sensor placement based on
greedy algorithm is adopted. None of these works consider
observability constraint which makes the problem NP-hard in
general, and this is the main distinction of our work. Next, we
extend to the networking cost optimization. The introductory
results on network design based on distributed estimation and
formulation of distributed observability are taken from [7],
[18]. As the next contribution, this paper generalizes the costoptimal design of sensor network for centralized estimation
[12], [13], [19], [20] to distributed case while the problem
is constraint with distributed observability of system/network.
Our results extends the leader selection scenario in [21] by
cosidering cost and distributed observability constraints. We
show that with bidirectional communications among sensors
the networking cost optimization has a polynomial order
solution. The most general case, where the communication
links are directional, is shown to be NP-hard. For this case, a 2approximation2 algorithm with polynomial complexity O(m2 )
is suggested.
II. P ROBLEM F ORMULATION
Consider estimation of LTI system with measurements:
xk+1
ykj

=
=

Axk + vk ,
Hj xk + rkj ,

j ∈ {1, ..., m}.

(1)
(2)

where x = [x1 . . . xn ]⊤ ∈ Rn is state-space, y =
[y1 , . . . , ym ] ∈ Rm is measurement vector, v and r, are
noise variables with standard assumptions on Gaussianity and
independence. Define Hj , the j-th row of H with dimention
1-by-n, as the measurement (row) matrix of sensor j, and
1 NP-hard problems are believed to have no solution in time-complexity
upper-bounded by a polynomial function of the input parameters.
2 An algorithm is ρ-approximation algorithm if it finds a solution within a
factor ρ of optimum solution.

2

ykj , the j-th column of yk , as measurement of sensor j.
Throughout the paper we may omit the time index k and use
y. Based on Kalman [22], bounded estimation error requires
(A, H)-observability. The system is monitored by a network
of sensors, denoted by GW . This paper considers single timescale distributed estimation over the sensor network, where
both system dynamics and distributed estimator evolve at the
same time-scale [1], [3]–[8], [10], [23]. In the single time-scale
distributed estimation method two types of information-fusion
are performed: (i) prediction-fusion, and (ii) measurement
fusion. It is known that if the system is structurally cyclic
(assumed in this paper), only prediction fusion is necessary
for monitoring the global state of the system, see [7], [8],
[24] for details. Every sensor shares the state prediction of the
system over the neighborhood, N , over the communication
network GW . Denoted by W the network adjacency matrix,
where Wij defines the consensus weight for prediction fusion.
Note that the entries in the adjacency matrix are defined such
that W is row-stochastic, see [7], [8], [10] for details. Note
that, in distributed estimation the global state of the system
is observable to every sensor via information-fusion over the
sensor network; this is called distributed observability and
implies that there exist a feedback gain matrix such that every
sensor achieves asymptotic omniscience on the global state of
the system and the error dynamics of sensors achieves global
asymptotic stability on Mean Squared Error (MSE) [7], [8],
[10]. This is formally stated in the following theorem:
Theorem 1. Given a structurally full-rank system matrix
A, measurement matrices Hi , i ∈ {1, ..., m}, communication
network of sensors GW , if (W ⊗ A, DH ) is observable the
system is distributed observable by the group of sensors, where
⊗ is the kronecker product and DH is defined as follows:

⊤
DH = blockdiag H1⊤ H1 , . . . , Hm
Hm
Recall that distributed observability implies that the system
is observable at each sensor. The general theorem with detailed
proof (irrespective of system structural rank) is given in [7],
[8], [24]. The proof for structurally full-rank systems is also
provided in [5], [10]. Note that this result is irrespective of
specific algorithms for distributed estimation and holds in general. In other words, structural observability of (W ⊗ A, DH )
is sufficient for existance of certain gain matrix for distributed
estimation protocol. Note that in this paper this condition
is structural-based, and the exact numerical values can be
determined based on specific esimation protocol.
The problem is to determine the structure of measurement/sensing matrix H and the network adjacency matrix
W such that (W ⊗ A, DH )-observability is satisfied. Note
that, as mentioned in the introduction, every choice of sensor measurement and communication network accompanies
with a cost. On the other hand, all possible communication
links among sensors are represented by the network Gnet .
As mentioned in the introduction, every link in Gnet has
a cost, referred to as networking cost. The problem is to
minimize both measurement/sensing cost and networking cost
(from possible communication links Gnet ) while satisfying
distributed observability of sensors. The problem is formally

described below:
Problem Formulation 1. For a group of sensors assume
sensing cost cij for every sensor yi , i ∈ {1, . . . , m} measuring
state xj , j ∈ {1, . . . , n}, and networking cost bij for communication from sensor yi to yj in Gnet . Given the network Gnet
and the cost matrices c and b the problem is to minimize
sensing and networking cost of monitoring the global state of
the dynamical system (1), leading to the following formulation:
argmin
H,W

n
m X
X
i=1 j=1

cij Hij +

m
m X
X

bij Wij

i=1 j=1

s.t. (W ⊗ A, DH )-observability,
GW ⊂ Gnet ,

(3)

Hij ∈ {0, 1}, Wij ∈ {0, 1}
A is structurally full rank
where A is system matrix, H is measurement matrix, W is
adjacency matrix of sensor network, H represents the 0-1
structure of H, and W represents the 0-1 structure of W .
The following assumptions are considered:
• Every sensor is assigned with only one measurement
(without loss of generality), and the number of sensors is
sufficient for system observability. Note that we assume
minimum number of sensors for observability; each sensor measures at least one state and there is no inactivated
sensor with no measurements.
• The given network Gnet representing all possible communications among sensors is Strongly Connected (SC).
• The optimization problem is solved, not by a leader node,
but by user once and then the sensor network is designed.
III. S TRUCTURAL R ELAXATION
In this section we provide some graph-theoretic concepts to
relax the observability constraint in Problem Formulation 1.
Reformulating the problem as known combinatorial problems,
the solution is provided in the next section. As mentioned in
the previous section, observability is required for estimation
of dynamical systems. This paper adopts a graph-theoretic observability method, called structural observability. It is known
that such methodology is irrespective of numerical values
of system parameters and only deals with system digraph
representing the zero-nonzero pattern of system matrix [15],
[18], [25]. Based on this methodology we relax the observability condition in equation (3) to structural observability.
This relaxation is valid since the set of values for which
structural observability does not match with observability lies
on algebraic subspace with zero Lebesgue measure [15]. Such
relaxation has been used in related literature [7], [12]–[14],
[18], [19], [21], [25]. Related graph-theoretic concepts for
structural observability are defined in the followings.
In Problem Formulation 1, consider A ∼ {0, 1}n×n as
the structured representation of system matrix A. Nonzero
elements of A are defined by system parameters, and the
zeros are system fixed zeros. Similarly, H ∼ {0, 1}m×n is
the structure of measurement matrix H. Hij being nonzero
implies measurement of state xj by sensor yi . In structured

3

systems theory, such zero-nonzero structure of A and H is
represented by a directed graph (digraph) Gsys ∼ (X ∪ Y, E),
which is referred to as system digraph. Note that, X is
the set of state nodes {x1 , . . . xn } each representing a state,
and Y is the output set {y1 , . . . ym } representing the sensor
measurements. The nonzero entry Aij is represented by an
edge xj → xi . The nonzero entry Hij is represented by an
edge xj → yi . Define a path as sequence of non-repeated
path
nodes connected by edges represented by −−−→. Denote by
path
−−−→ Y a path that ends in an output node in Y. A path that
starts and ends at the same node is called a cycle.
A graph is called Strongly Connected (SC) if there is a path
from every state xi to every other state xj . If the graph is not
SC it can be decomposed to Strongly Connected Components
(SCC). Note that states in a SCC are mutually reachable, i.e.
there is a path from every state to every other state in that
SCC. In order to explore states necessary for observability,
we partition all SCCs in terms of their reachability by states
in other SCCs. In this direction, SCC that has no outgoing
edges to other SCCs is called parent SCC. In other words,
for SCCl if for all xi ∈ SCCl there is no xj ∈
/ SCCl such
that xi → xj , then SCCl is a parent SCC. A non-parent
SCC is called a child SCC. In other words, if SCCl is a
child SCC there exist xi ∈ SCCl and xj ∈
/ SCCl such that
xi → xj . Using this classification we state the main theorem
on structural observability of structurally cyclic system3 .
Theorem 2. Given a structurally cyclic system, the system is
structurally observable if and only if one state in every parent
SCC is measured by a sensor, i.e. for every parent SCCl there
exist xi ∈ SCCl such that xi → Y.
See detailed proof in our previous work [7], [18].
This theorem further implies that the number of necessary
sensors for observability equals the number of parent SCCs
in structurally cyclic systems. In this direction, assigning a
sensor measurement to every parent SCC satisfies structural
observability. Parent SCCs do not share any state node. Note
that Parent SCCs (in general all SCCs) do not share any state
node. , and there are polynomial time algorithms to decompose
the system digraph into disjoint SCCs and define their type
(parent or child), namely Depth First Search (DFS) algorithm
[26] with computational complexity of O(m2 ).
Next, we extend the structural observability to distributed
case. Note that to recover distributed observability at every
sensor the network GW must be designed such that the system
is observable to each sensor. Notice that the proper network
design along with stochasticity of network adjacency matrix is
sufficient for distributed observability. The sufficient condition
on the network design is stated in the following theorem:
Theorem 3. For the system digraph, Gsys let the sensors have
the necessary measurements based on Theorem 2, i.e. every
sensor has a measurement of a (distinct) parent SCC. The
system is distributed observable in structural sense if for every
sensor there is a directed path in the network to every other
sensor, i.e. the sensor network GW is SC.
3 A system is structurally cyclic if there is a family of cycles spanning all
state nodes. For such system the system matrix A is full-rank.

The proof follows from the output-connectivity condition
of structural observability. Note that for observability there
must be a directed path from every parent SCC to every
sensor. Since (i) there is a link from a state in every parent
SCC to a distinct sensor node, i.e. for SCCl → yi , and also
there is a path from every sensor node to every other sensor
path
node, i.e. yi −−−→ yj for j ∈ {1, ..., m}. Therefore for every
SCCl , l ∈ {1, ..., m} there is a path to every sensor node
yi , i ∈ {1, ..., m}. See detailed proof in [7], [10], [18].
Notice that since
the costs cij and
are positive, the
PmallP
PmbijP
n
m
minimization of i=1 j=1 cij Hij +P i=1 P j=1 bij Wij can
n
m
be separarted into
of
j=1 cij Hij and
i=1
Pm
Pmminimization
minimization of i=1 j=1 bij Wij . Second, based on Theorem 2 and 3, the distributed observability constraint is equivalent to (i) having one sensor measurement from each parent
SCC for structural observability of (A, H) (Theorem 2), and
(ii) having the network of these sensors to be SC (Theorem 3).
Note that, P
the first
(i) is related to sensing cost opPconstraint
n
timization m
c
H
constraint (ii)
i=1
j=1 ij ij while the second
P
P
m
is related to networking cost optimization m
i=1
j=1 bij Wij .
Therefere both optimization and constraint can be decomposed
into separate cost optimization problems, which results in an
exactly equivalent formulation as follows:
Problem Formulation 2. P1. For a group of sensors with c
as the measurement cost matrix, the problem is to minimize
sensing cost of the dynamical system (1):
argmin
H

m X
n
X

cij Hij

i=1 j=1

s.t. (A, H)-structural observability,

(4)

Hij ∈ {0, 1}
A is structurally full rank
P2. For the network of sensors with b as the link cost matrix
of Gnet , the problem is to minimize the networking cost as:
argmin
W

m X
m
X

bij Wij

i=1 j=1

s.t. GW ⊂ Gnet , GW is SC
Wij ∈ {0, 1}

(5)

IV. C OMBINATORIAL O PTIMIZATION S OLUTION
A. Solution to Problem P1
In this subsection, we solve the sensing cost optimization P1 (for structurally full-rank systems). This problem is
claimed to be NP-hard for general systems in [14]. However,
here we provide a polynomial order solution for P1 for
structurally cyclic systems. To minimize the sensing cost for
estimation, the assumption is that the number of sensors
equals the number of necessary measurements for structural
observability. The minimal number of sensors for observability
is primarily addressed in our previous work [8], [24], [27].
As mentioned in Section III and following the stated assumptions, the minimum number of sensors for structurally
full-rank systems equals the number of parent SCCs in the
system digraph, resulting the following formulation:

4

Problem Formulation 3. P1. Considering minimum number
of sensor measurements for observability, the sensing cost
optimization problem takes the following form:
m X
n
X

argmin
H

B. Solution to Problem P2
cij Hij

i=1 j=1

s.t. (A, H)-structural observability,
n
m
X
X
Hij = 1
Hij ≤ 1,

(6)

j=1

i=1

Hij ∈ {0, 1}
The extra conditions doPnot change the optimization probm
lem. The added constraint i=1 Hij ≤ 1 implies
Pnthat all states
are measured by at most one sensor, and
j=1 Hij = 1
follows the assumption that every sensor takes one state
measurement. Next, following the fact that parent SCCs are
separate components, the problem can be reformulated as
assigning a group of sensors to take measurement of a group
of parent SCCs. For this formulation, let define a new cost
matrix Cm×m , where Cij denotes the cost of assigning a
parent, SCCj , to sensor yi . This cost is defined as the
minimum sensing cost among all states in parent SCCj , i.e.
Cij = min{cil }, xl ∈ SCCj , i, j ∈ {1, . . . , m} The above
equation reformulates matrix cm×n to matrix Cm×m . In other
words, the cost matrix relating sensors to states is transferred
to cost matrix relating sensors to parent SCCs. In this direction,
we introduce a new structured matrix Z ∼ {0, 1}m×m. This
matrix defines the assignment of sensors to parent SCCs, i.e.
Zij 6= 0 implies a state in SCCj is measured by sensor
i (SCCj → yi ). By recalling Theorem 2, observability is
guaranteed by sensing all parent SCCs. Hence, following setup
represents the new formulation of original problem P1:
Problem Formulation 4. P1. let have m sensors to be
assigned to m parent SCCs in a structurally cyclic systems;
the sensing cost optimization is reformulated as:
argmin
Z

s.t.

entries) and structural results consists with the LSAP, the
relaxed solution is exact and the gap is zero.

m X
m
X

(Cij Zij )

i=1 j=1
m
X

m
X

j=1

i=1

Zij = 1,

Zij = 1

(7)

Zij ∈ {0, 1}
Pm
The new constraint j=1 Zij = 1 means that every parent
SCC is measured, which guarantees observability. Note that,
formulation (7) represents a famous combinatorial optimization problem, known as Linear Sum Assignment Problem
(LSAP) [28]. The most recent and most computationally
efficient solution to the LSAP is known as Hungarian method
proposed in [29] with the complexity order of O(m3 ). Therefore, noting that Problem Formulation 4 represents the relaxation to original problem P1 in Problem Formulation 2,
the sensing cost optimization P1 finds a polynomial order
solution. Note that structural relaxations hold for almost all
numerical values of system parameters [15]. In other words,
for any choice of system/measurement/network matrices as
long as the structures are fixed (with potentially time-varying

In this subsection, we discuss the solution for networking
cost optimization problem P2 stated by equation (5). Recall
that in this problem the goal is to find the minimum cost
Strongly-Connected (SC) subgraph spanning network Gnet .
We separately discuss the solution of P2 for (i) undirected
networks, and (ii) directed networks.
Undirected network Gnet : Consider the case that every
communication link in network of sensors is bidirectional and
the networking cost matrix b is symmetric. Note that in this
case we assume the sensors share their information mutually,
i.e. sensor i shares its prediction with sensor j if and only if
sensor j shares its prediction with i. In this case, P2 represents a known problem in combinatorial optimization and is
equivalent to the Minimum Spanning Tree (MST) or Minimum
Weight Spanning Tree problem [30]. This problem is known
to have polynomial order solution using Prim’s algorithm [31]
(or Kruskal’s algorithm [32]). Given the adjacency matrix of
Gnet the computational complexity of the Prim’s algorithm is
O(m2 ). Note that, similar to the solution to P1, in this case
the structural relaxed solution based on Kruskal’s or Prim’s
algorithm is exact and the gap is zero.
Directed network Gnet : Consider the case that the network
links are directed and Gnet represents a directed graph (digraph). In this case, P2 represents the Minimum Spanning
Strong Sub(di)graph (MSSS) problem, which is known to
be NP-hard [33]4 . Approximations to solve this problem are
proposed in the literature. In [34], the authors proposed a
polynomial-time algorithm as follows: fix a root node of
the directed network and then find the in-branching (also
known as arborescence) and out-branching5 and take the union
of the two branching as the MSSS. Note that the cost of
each branching in worst case equals to MSSS. Therefore the
output of this approach gives an approximation at factor of
2. Edmond’s algorithm [35] is the efficient way to find the
in/out-branching with computational complexity of O(m2 ).
Let define gap as follows: if F is the outcome of the relaxed
algorithm in worst-case (i.e. the upper-bound for the solution)
and L is the exact minimal solution, the gap is defined as:
F −L
L . Then the gap of the Edmond’s algorithm is 1.
V. C ONCLUSION
In this paper, we proved a polynomial order solution of
complexity O(m3 ) for sensing cost optimization in structurally full-rank systems. A 2-approximation polynomial order
solution (with gap 1) with O(m2 ) complexity is provided
for generally NP-hard networking cost optimization. Further,
considering undirected network of sensors an exact polynomial
order O(m2 ) solution is proposed for this problem.
4 It is known that the MSSS problem generalizes the Hamiltonian-Cycle
problem and therefore is NP-hard [33].
5 The in-branching is a generalization of MST to digraphs where each node
has a minimum cost directed path to the root node. The out-branching is the
reverse problem where the root node has minimum cost directed path to every
other node [33].

5

R EFERENCES
[1] S. Das and J. M. F. Moura, “Consensus+ innovations distributed kalman
filter with optimized gains,” IEEE Transactions on Signal Processing,
vol. 65, no. 2, pp. 467–481, 2017.
[2] A. Mohammadi and A. Asif, “Distributed consensus + innovation particle filtering for bearing/range tracking with communication constraints,”
IEEE Transactions on Signal Processing, vol. 63, no. 3, pp. 620–635,
2015.
[3] S. Das and J. M. F. Moura, “Distributed kalman filtering with dynamic
observations consensus,” IEEE Transactions on Signal Processing, vol.
63, no. 17, pp. 4458–4473, 2015.
[4] S. Tu and A. Sayed, “Diffusion strategies outperform consensus
strategies for distributed estimation over adaptive networks,” IEEE
Transactions on Signal Processing,, vol. 60, no. 12, pp. 6217–6234,
2012.
[5] F. S. Cattivelli and A. H. Sayed, “Distributed detection over adaptive
networks using diffusion adaptation,” IEEE Transactions on Signal
Processing, vol. 59, no. 5, pp. 1917–1932, May 2011.
[6] S. Kar and J. M. F. Moura, “Consensus+ innovations distributed
inference over networks: cooperation and sensing in networked systems,”
IEEE Signal Processing Magazine, vol. 30, no. 3, pp. 99–109, 2013.
[7] M. Doostmohammadian and U. Khan, “On the genericity properties in
distributed estimation: Topology design and sensor placement,” IEEE
Journal of Selected Topics in Signal Processing, vol. 7, no. 2, pp. 195–
204, 2013.
[8] M. Doostmohammadian and U. Khan, “Graph-theoretic distributed
inference in social networks,” IEEE Journal of Selected Topics in Signal
Processing, vol. 8, no. 4, pp. 613–623, Aug. 2014.
[9] G. Battistelli, L. Chisci, G. Mugnai, A. Farina, and A. Graziano,
“Consensus-based algorithms for distributed filtering,” in 51st IEEE
Conference on Decision and Control, 2012, pp. 794–799.
[10] S. Park and N. Martins, “Necessary and sufficient conditions for the
stabilizability of a class of LTI distributed observers,” in 51st IEEE
Conference on Decision and Control, 2012, pp. 7431–7436.
[11] M. Doostmohammadian, H. R. Rabiee, H. Zarrabi, and U. A. Khan,
“Distributed estimation recovery under sensor failure,” IEEE Signal
Processing Letters, vol. 24, no. 10, pp. 1532–1536, 2017.
[12] S. Kruzick, S. Pequito, S. Kar, J. Moura, and A. Aguiar, “Structurally
observable distributed networks of agents under cost and robustness
constraints,” IEEE Transactions on Signal and Information Processing
over Networks, 2017.
[13] S. Pequito, S. Kruzick, S. Kar, J. M. F. Moura, and A. P. Aguiar,
“Optimal design of distributed sensor networks for field reconstruction,”
in 21st IEEE European Signal Processing Conference, 2013, pp. 1–5.
[14] S. Pequito, S. Kar, and A. P. Aguiar, “Minimum number of information
gatherers to ensure full observability of a dynamic social network: a
structural systems approach,” in IEEE 2nd Global Conference on Signal
and Information Processing, Atlanta, GA, Dec. 2014.
[15] J. M. Dion, C. Commault, and J. van der Woude, “Generic properties
and control of linear structured systems: A survey,” Automatica, vol.
39, pp. 1125–1144, Mar. 2003.
[16] S. Joshi and S. Boyd, “Sensor selection via convex optimization,” IEEE
Transactions on Signal Processing, vol. 57, no. 2, pp. 451–462, 2009.
[17] A. Krause, C. Guestrin, A. Gupta, and J. Kleinberg, “Near-optimal
sensor placements: Maximizing information while minimizing communication cost,” in Proceedings of the 5th international conference on
Information processing in sensor networks. ACM, 2006, pp. 2–10.
[18] M. Doostmohammadian and U. A. Khan, “Communication strategies
to ensure generic networked observability in multi-agent systems,” in
45th Annual Asilomar Conference on Signals, Systems, and Computers,
Pacific Grove, CA, Nov. 2011, pp. 1865–1868.
[19] S. Pequito, F. Rego, S. Kar, A. P. Aguiar, A. Pascoal, and C. Jones,
“Optimal design of observable multi-agent networks: A structural system
approach,” in IEEE European Control Conference, 2014, pp. 1536–1541.
[20] S. Pequito, S. Kar, S. Sundaram, and A. P. Aguiar, “Design of communication networks for distributed computation with privacy guarantees,”
in IEEE 53rd Annual Conference on Decision and Control (CDC), 2014,
pp. 1370–1376.
[21] S. Pequito, V. Preciado, and G. J. Pappas, “Distributed leader selection,”
in 54th IEEE Conference on Decision and Control (CDC), 2015, pp.
962–967.
[22] R. Kalman and R. Bucy, “New results in linear filtering and prediction
theory,” ASME Journal of Basic Engineering, vol. 83, pp. 95–108, 1961.
[23] T. Boukhobza, F. Hamelin, S. Martinez-Martinez, and D. Sauter, “Structural analysis of the partial state and input observability for structured

[24]
[25]
[26]
[27]

[28]
[29]
[30]
[31]
[32]
[33]
[34]
[35]

linear systems: Application to distributed systems,” European Journal
of Control, vol. 15, no. 5, pp. 503–516, Oct. 2009.
M. Doostmohammadian and U. A. Khan, “On the characterization of
distributed observability from first principles,” in 2nd IEEE Global
Conference on Signal and Information Processing, 2014, pp. 914–917.
Y. Y. Liu, J. J. Slotine, and A. L. Barabási, “Observability of complex
systems,” Proceedings of the National Academy of Sciences, vol. 110,
no. 7, pp. 2460–2465, 2013.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction
to Algorithms, MIT Press, 2009.
M. Doostmohammadian and U. A. Khan, “Measurement partitioning
and observational equivalence in state estimation,” in IEEE International
Conference on Acoustics, Speech and Signal Processing (ICASSP), 2016,
pp. 4855–4859.
D. W. Pentico, “Assignment problems: A golden anniversary survey,”
European Journal of Operational Research, vol. 176, no. 2, pp. 774–793,
2007.
J. Edmonds and R. Karp, “Theoretical improvements in algorithmic
efficiency for network flow problems,” Journal of the Association for
Computing Machinery, vol. 19, pp. 248–264, 1972.
H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, “Efficient algorithms for finding minimum spanning trees in undirected and directed
graphs,” Combinatorica, vol. 6, no. 2, pp. 109–122, 1986.
R. C. Prim, “Shortest connection networks and some generalizations,”
Bell Labs Technical Journal, vol. 36, no. 6, pp. 1389–1401, 1957.
J. B. Kruskal, “On the shortest spanning subtree of a graph and the
traveling salesman problem,” Proceedings of the American Mathematical
society, vol. 7, no. 1, pp. 48–50, 1956.
J. Bang-Jensen and G. Z. Gutin, Digraphs: theory, algorithms and
applications, Springer Science & Business Media, 2008.
G. N. Frederickson and J. JaJa, “Approximation algorithms for several
graph augmentation problems,” SIAM Journal on Computing, vol. 10,
no. 2, pp. 270–283, 1981.
J. Edmonds, “Optimum branchings,” Journal of Research of the National
Bureau of Standards B, vol. 71, no. 4, pp. 233–240, 1967.

