Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I'm not sure I understand the second sentence of the second paragraph. What is a valid path, exactly? –  Qiaochu Yuan Sep 1 '10 at 4:44
    
Edges are not scalars. Edges are relations between two nodes. e.g. suppose if (u,v) is an edge in a graph then they are related by some function f(u) = v. u, v and f can be anything. e.g. u and v can be column vectors and f can be a matrix. I am not sure I understand your question properly. –  Pratik Deoghare Sep 1 '10 at 4:56
    
@TheMachineCharmer: I believe nai is referring to the weights on the edges, e.g. the entries in the adjacency matrix. –  Qiaochu Yuan Sep 1 '10 at 5:55
    
@Qiaochu Yuan:humm.. you are right. I don't know if theory exists to take care of this. But I think it must be perfectly valid to assign non-scalars as weights. e.g. in finite state machine they are transition conditions; also if u,v are vectors we can use u-v as 'weight'. In general, I think we can assign whatever we want to edges,nodes or weights if we can assign meanings to them and be able to interpret without getting into trouble. –  Pratik Deoghare Sep 1 '10 at 6:54
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? –  Tsuyoshi Ito Sep 1 '10 at 15:02

2 Answers 2

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.

share|improve this answer
    
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!? –  nai Sep 1 '10 at 22:52

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 requierements 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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