Skip to main content

All Questions

Filter by
Sorted by
Tagged with
10 votes
1 answer
411 views

Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$. Now add edge-pair ...
Brendan McKay's user avatar
5 votes
1 answer
183 views

Resource Constrained Routing with Refueling

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity? Especially modeling ...
Manfred Weis's user avatar
  • 13.2k
5 votes
0 answers
581 views

When is polytope compatible with network flow?

A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
David Harris's user avatar
  • 3,475
4 votes
2 answers
314 views

Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
Sanchayan Dutta's user avatar
2 votes
4 answers
212 views

Efficient algorithm for graph problem

Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
Martin Clever's user avatar
1 vote
0 answers
20 views

Calculating Cost-Optimal 1-Factors in Digraphs

I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...
Manfred Weis's user avatar
  • 13.2k