1
$\begingroup$

Consider a network $ G(V,E) $ with vertex set $V$ and number of edges $E$ being formed by a pre-defined formation process, with one edge being placed in each step. Now, a k-path is defined as

$(i,j) \in {G \quad s.t \quad x_{ij} = 0 \quad and\quad (x_{im_1} = x_{jm_1} = 1) , .... , (x_{im_k} = x_{jm_k} = 1)} $

$x_{ij} = 1$ if an edge exists between nodes i and j and is 0 otherwise

I'm trying to come up with an efficient algorithm to update the set of k-paths ($ k \in {1,2,3}$) with each step in the network formation process.

So far, what I've been doing is pretty inefficient, in that I loop through all the edges to return the list of k-paths at every stage. But I imagine that I will be able to start with an empty network (having all edges belonging to the set of 0-paths) and then developing some scheme to update the elements in the sets (all the sets of higher order k-paths will be Null sets in the beginning).

$\endgroup$
1
$\begingroup$

I'm assuming this is a simple graph. Paths of length $1$ are easy. You have that with the adjacency matrix. Paths of length $2$ are equally easy, assuming a simple graph. You simply take the sum of the non-diagonal entries in the upper (or lower) triangular half of $A^{2}$, for $A$ being the adjacency matrix of your graph. $A^{2}$ counts the number of two-walks. Since $G$ is simple, the only two-walks are $P_{2}$, a path of length $2$ (which are counted by the non-diagonal entries); or walking twice along the same edge (in which case, the diagonal entries count the edges). You only consider one half of the matrix, as $A^{n}$ for $n \in \mathbb{N}$ is skew-symmetric. I'll have to think more on $k = 3$.

If you don't mind my asking, could you expand perhaps on your rationale for trying to cache all the paths of $G$, partitioning them by length? I'm wondering if there might be a better way to obtain the same result without the caching.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.