# Tagged Questions

**1**

vote

**1**answer

204 views

### Is this Graph parameter known?

Let $\lambda(G)$ denote the edge-connectivity of $G$.
Consider the following parameter:
$\rho(G) = \max_{X \subset V(G)} \min(\lambda(G[X]), \lambda(G[V(G) - X]))$
Has this parameter been studied? ...

**-1**

votes

**1**answer

50 views

### Effect of a Specific Restriction on the Integrality of Min-cost Flow Solutions

I want to model the following situation: there is one production site (modelled by the source), a collection of depots (modelled by nodes without demand) and, of course many more customers (modelled ...

**0**

votes

**1**answer

488 views

### Finding the lowest cost set of disjoint paths using all nodes in a directed graph?

I have a directed graph with edges connecting nodes representing costs.
I wish to find the set of paths which
-go from node 'start' to node 'end'
-are node-disjoint (except for the start and end ...

**3**

votes

**0**answers

330 views

### Minimum weight bipartite graph clique covering

I was wondering if anyone here could give me any pointers as to how to solve the following problem.
Let $B=(L,R,E)$ be a bipartite graph, and $\forall u\in L\cup R$, let $c_u$ be a cost associated to ...

**6**

votes

**1**answer

378 views

### How does this algorithmic proof of Edmonds-Gallai work?

Sorry, this is going to be technical and dirty. I am not looking for a proof of the Edmonds-Gallai structure theorem (I understand two of them, even if they are rather similar); I am trying to ...

**14**

votes

**0**answers

572 views

### A Conjecture About Directed Graphs that are the Union of Two Trees

Let D=(V,E) be a directed graph that is the union of two edge-disjoint directed
spanning trees. Suppose that
There no subset X of vertices so that
there is precisely one directed edge
from X ...