| 
| 
| 
| 
| 
i 
| 
| 
| 
I 
| 
  
  
A 
SS 
  
  
—DRe 
  
  
  
  
NIE 
  
  
Oa 
te 
= 
sus 
"t 
{ 
  
  
  
  
EN 
fs 
x 
d 
s AN 
L 
  
Figure 4: Detection and isolation of a 4-distance connected subgraph. 
An example of detection/isolation of a 4-distance 
connected subgraph with the composed filter A? o /* 
is given in Figure 4. 
6.4 On algorithms for minimal weight bases 
A major drawback of the discrete filters proposed 
in the former section is the lack of fast algorithms 
for finding cycle bases of minimal length. In 1987, 
J.D.Horton published the first algorithm for con- 
structing minimal weight cycle bases [10]. Although it 
is a very expensive algorithm —it takes time O(m?n), 
for a graph of order n and size m— it has the bene- 
fit of showing that the problem of finding a minimal 
cycle basis is not NP-complete. 
As Horton writes in his paper, £here is considerable 
room for improvement on this problem. In particular, 
it remains an open question whether a faster algo- 
rithm for [sparse] graphs do exists. 
7 HINTS FOR NUMBERING 
ALGORITHMS 
A practical way to deal with the numbering of com- 
plex graph structures is to build up the numbering 
map p: V(G) — N in n steps, which is equivalent 
to build q where 
q:V(G) — Nx ^. xN, (2) 
and then identify the natural order in N with the 
lexicographic order in N™. 
If q(v) — (am(v),...,q»(v)), the sets Ij, I, = 
{a:(v)}vev(e) are computed succesively for i = 
1,...,n according to different criteria set for each 
620 
step. An example for such criteria sequence could 
be as follows. 
1. Compute the connected components C1,... , Cm 
of G; qu(v) = k if v is a vertex of the connected 
component Ck. 
2. For each i € I, consider the subgraph 
G((v:a(v) — i) 
set qo(v) — 2 if v is a border vertex (Section 2.1) 
or almost (a vertex with too many adjacent ver- 
tices according to some relative threshold). 
3. Consider the family of subgraphs 
G((v: a (v) 7$ qx(v) — 33), 
for alli € Iı and j € I2. Try to apply some of the 
techniques described; for instance, check for bi- 
partiteness, look for high nonlocality values, etc. 
4. Consider the family of subgraphs 
G({v: q1(v) = 4, ax(v) 7 j, as(v) — kj), 
for all i € I, j € I, and k € I3. Apply to each 
subgraph nested disection or any algorithm you 
might prefer. 
5. s 
Note that the former sequence is just an example for 
the sake of illustrating the idea, and that it can be 
further refined if one has the algorithmic tools to do 
it. A possibility is to devote some step m to assign 
values to {gm (v)}vev(c) according to a priori known 
information on the network which might come from 
a previous adjustment, from approximate algorithms 
or 
CO 
on 
ab 
ize 
ble 
sol 
for 
ide