0
$\begingroup$

I am working on finding shortest disjoint path problem, When there are distinct origin destination pairs and there is a predefined time window (or length) associated with each object (which we want to move from one origin to its specific destination). This time window will tell us how long it will take for the object to pass a particular point on the network.

These objects should not encounter each other in any ways on the network, so it is a vertex-disjoint path problem with respect to time. For example if I have two objects A and B, and object A will pass node 1 from 10:00 a.m. to 12 p.m., during these time periods object B cannot cross this node, but any time after 12.00 and before 10 (as long as the time window of B allowed) B can pass through node 1.

I want to know if there is any application of this problem in computer science?

$\endgroup$
  • 2
    $\begingroup$ I can't tell what you're asking. Isn't the vehicle routing problem part of computer science? So isn't that already an application of the vertex-disjoint paths problem in CS? And your title talks about time windows but I don't see that anywhere in the question. $\endgroup$ – David Richerby Apr 29 '15 at 7:43
  • 1
    $\begingroup$ I, too, have trouble understanding what you are proposing. Mind that as soon as you do properly define your problem, it is a computer science problem. Do you mean to ask if it has been studied before? We can't answer that until you give a clearer problem description. What exactly are the inputs and outputs? (It does remind me of network flow problems.) $\endgroup$ – Raphael Apr 29 '15 at 9:01
  • $\begingroup$ @DavidRicherby I edited my question, I hope it helps this time. Please let me know if you still have question. $\endgroup$ – azar Apr 29 '15 at 14:41
  • $\begingroup$ @Raphael I edited my question. I want to know if there is any situation in computer science which is somehow related to this problem. For example in communication problems or parallel computing ? My major is not computer science and I am urged to find an application for this problem. $\endgroup$ – azar Apr 29 '15 at 14:42
  • 1
    $\begingroup$ The search for node- resp. edge-disjoint paths has definitely been studied; you may want to search for that term. I think we even have some questions about that on this site. As for "real" applications, I don't know; that's not my area of expertise. $\endgroup$ – Raphael Apr 29 '15 at 14:52
1
$\begingroup$

Your problem is not clearly defined, but it's likely it can be solved by running a standard algorithm on a longer graph.

If $G=(V,E)$ is your original graph, build $G'=(V',E')$ by making $t$ copies of each vertex in $G$, one per time slot (where there are $t$ time slots): call the copies $v_1,\dots,v_t$. Now for each vertex $v \in V$, add an edge $v_i \to v_{i+1}$ for each $i$ (this corresponds to an object staying at vertex $v$ throughout time slot $i$). Also, for each edge $(v,w) \in V$, add an edge $v_i \to w_{i+1}$ for each $i$ (this corresponds to an object moving from vertex $v$ to $w$).

Now you're looking for vertex-disjoint paths in $G'$. There are standard algorithms for finding vertex-disjoint paths in $G'$ (e.g., using network flow or other methods). If you want a collection of shortest vertex-disjoint paths, that might be possible, but you'll need to define precisely what objective function you want to minimize before we can suggest an algorithm.


This general approach can likely accommodate many additional requirements, such as that traversing a particular edge takes a certain amount of time (just use that as the length on the edge), or that we don't know the starting time when each object enters the system (add a source vertex for each object, with edges from the source to each place that the object might enter the system).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer, but this is not my question. You have to guarantee that the object will take for example t1 time on the first edge and t2 for the second and you don't know the starting time, So if you just simply add those vertices and edges, you just will increase the difficulty of the graph, because you have to have specific graph topology for each scenario that you want to make. On the other hand, my question is about the real application of this model in computer science, if there is any. $\endgroup$ – azar Apr 30 '15 at 17:03
  • $\begingroup$ @azar, none of that is in your question. We can't be expected to answer your question if you don't state the problem precisely and list all requirements! It's not just me; you've received multiple requests for clarification in the comments. Please edit the question to state the problem more precisely and carefully, and list all requirements. A helpful way to describe an algorithmic problem is to list the set of inputs to the algorithm, the desired output from the algorithm, and what properties you want the output to have. $\endgroup$ – D.W. Apr 30 '15 at 19:46

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.