5
$\begingroup$

Can someone please point me in the direction of any theory on graphs where the edge weights are not scalars but represent some relation between the nodes that is a simple function of a single variable (simple, say piecewise linear).

In particular, I'm interested in various basic graph properties and also thinking of the graph as representing a network. So, for example, if the graph represented a communication network over time then the edge weights would be a function represented connectivity as a function of time, how do you find a valid path between nodes? I'm looking for help both on specific algorithms but also general theory if it exists?

I'm aware of time-extended networks where you explicitly expand out the dependence on the variable but, from what I've read, this incomplete and of limited applicability.

  • 1
    Can you edit the title and the text of the question to clarify that you are considering the case where edge _weights_ are functions?2010-09-01

2 Answers 2

3

So, basically you have a graph G that varies over time.

    1    2    3 1  f11  f12  f13 2  f21  f22  f23 3  f31  f32  f33 

Evaluate $f_{ij}(t)$ for $t$ to get $G(t)$ graph at time t.

Then you can use graph traversal algorithms like Depth-First Search, Breadth-First Search etc. for finding out which nodes are reachable.

However if you are allowing traveler to wait at nodes then problem becomes more difficult.

You can create one big graph by connecting G(t) for various time values. You can keep that graph small if you can limit time to wait at each node. If you know period of $f_{ij}(t)$ then also you can simplify this.

  • 0
    Thanks TheMachineCharmer, this is roughly what I've been using so far but it doesn't scale or generalize well. I'm hoping someone knows of a more general approach, perhaps it's not even in the field of graph theory!?2010-09-01
2

I came across a similar problem of using non-scalars as edge weights (vectors in my special case) and got to the conclusion that this is valid as long as you can define a total order on the edge weights and they are elements from a vector space that implements a linear operator.

The linearity together with the total order gives you characteristics of a equivalence relation, e. g. the transitivity that we need to get the weight of paths, since we can't just 'add up' the weights of the edges in the path.

Algorithms rely on that order (that is inherent in scalars). E. g. dijkstra that picks a unvisited node with the minimum distance. If those requirements are met one can easily adjust the algorithms to be applied to that graph instance.


More specific change the algorithms that you use to keep track of time (or introduce time steps that increase after each piece of solution your algorithm derived) and evaluate the edge functions each time you need them. If the functions do not take up too much computation time, you should be fine.