# Tag Info

## Hot answers tagged routing

5 votes
Accepted

### Distance Vector Routing Example

Let us review the specification of the algorithm. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between ...
• 39k
5 votes

### How do web browsers find out the MAC address?

So, how does the computer find out the MAC address of the server? It doesn't. The MAC address only has validity inside a local area network (LAN), which, as the name says, is local. Unless the ...
• 5,027
3 votes
Accepted

### why use bellman-ford instead of Dijstra in RIP routing?

Bellmon Ford is used by distance vector routing protocol (DVR). In DVR technique router keep knowledge of only next router which is adjacent that's why exchange of routing database only with neighbors....
• 317
3 votes
Accepted

### Why use private IP addresses in a LAN instead of MAC address

It's not an "instead". Every packet that is sent using IP contains both a MAC address and an IP address. You need both, because the IP-layer protocol stack understands only IP addresses, ...
• 159k
3 votes

### Routing algorithm for train network

Here is a list of algorithms that might help you: RAPTOR : Is an algorithm developed by Microsoft and is not graph based. RAPTOR produce pareto optimal results unlike CSA. Connection Scan Algorithm: ...
• 131
2 votes

### How can simulated annealing be related to the vehicle routing problem?

Simulated annealing is an optimization paradigm, in which (very roughly speaking) you start with some solution, and then try to make local changes that improve it, sometimes making a local change even ...
• 277k
2 votes

### Shortest Path using at most k colors

Here is a reduction from SAT to your problem. Let $\phi = C_1 \land \cdots \land C_m$ be a CNF on the variables $x_1,\ldots,x_n$. Consider the following graph with parallel edges (those can be easily ...
• 277k
2 votes
Accepted

### Finding path with specific length in weighted graph

Your problem is NP-complete by a reduction from Hamiltonian $st$-path, even with unweighted arcs. Thus, you should not expect a polynomial-time algorithm. I'll sketch a reduction below. Let $G$ be an ...
• 22.6k
2 votes

### Raptor algorithm: find next best paths

There are standard algorithms for finding the $k$ shortest paths in a graph: you provide $k$, and it returns the shortest path, second-shortest path, ..., up to the $k$th shortest path. See https://...
• 159k
2 votes

### Multi-Path Length Minimization

You can solve this optimally in $O(kn^3)$ time by solving a sequence of $k$ Assignment problems. Let $f(i)$ be the lowest sum of costs of any set of $n$ paths beginning at step $i$ and continuing to ...
• 5,479
1 vote

### Count-to-infinity avoidance techniques and hold-down timeout based question

Holddown Timer is another loop-prevention mechanism employed by distance vector routing protocol($DVR$). This feature prevents a router from learning new information about a failed route. When a ...
• 498
1 vote

### Seek to infer "correct" route from sequence of stops

To be clear, this is not an optimization problem; I do not seed to find the "best" route. Actually this is an optimization problem! Just instead of optimizing for shortest length or fastest time, ...
• 1,351
1 vote

### Trying to understand a Router's Forwarding Table

the router should choose the longest prefix match, or the most specific prefix that matches. so, here it will choose line 2, because of longest prefix (24 bit).
• 199
1 vote

### Route finding on a graph that must go through multiple edges

The statement that you want a path that "goes through multiple edges" is easily replaced with a normal path finding algorithm when you observe that you can subdivide each edge containing a ...
• 16.1k
1 vote

### Route finding on a graph that must go through multiple edges

I have decided that the best solution to this is a variation on Dijkstra's algorithm. Since it doesn't require a Hamiltonian Circuit and makes it easy to manage the weights. I will also use ...
1 vote

### Finding stages in routing algorithm

I don't know whether there is an efficient (polynomial-time) algorithm for this problem. I wouldn't be surprised if it is NP-hard. One approach would be to formulate this as an instance of integer ...
• 159k
1 vote

### How do web browsers find out the MAC address?

Your computer sends a request to your router, and the router sends it to the IP address of the server. Included in the request is your router’s IP address. So the server sends the website to your ...
• 30k
1 vote

### In "multi hop" network, is computer => computer 0 hop or 1 hop?

As stated on this site: A hop is a computer networking term that refers to the number of routers that a packet (a portion of data) passes through from its source to its destination. Sometimes a ...
• 321
1 vote
Accepted

### Combinatorial Optimization: Shortest distance given sets of drivers and riders

These kinds of scheduling problems tend to be hard (e.g., NP-hard to solve exactly; and messy because of all of the different constraints you have). My favorite "big hammer" for this kind of ...
• 159k
1 vote

### route and/or packing optimization algorithm

This specific problem seems to be an variation of minimizing the makespan in the job shop scheduling problem. Essentially, your couriers are modeled as 'workers' that need to process certain 'tasks', ...
• 8,248
1 vote

### Raptor Algorithm: Differences between trip and route

Be careful, as the definition of route given in this paper does not seems to match the definition given in other standards (namely, GTFS). In GTFS a route is a somehow arbitrary collection of trips, ...
1 vote

### Algorithm for finding the best “route” of tasks

If you have just one person to complete the tasks, this is the (in)famous Travelling Salesman Problem (TSP), which is NP-complete, so an efficient exact algorithm is a very remote possibility. Unless ...
• 14k

Only top scored, non community-wiki answers of a minimum length are eligible