Contributed Session Thu.3.H 3012

Thursday, 15:15 - 16:45 h, Room: H 3012

Cluster 2: Combinatorial optimization [...]

Arborescences

 

Chair: Attila BernĂ¡th

 

 

Thursday, 15:15 - 15:40 h, Room: H 3012, Talk 1

Attila BernĂ¡th
Covering minimum cost arborescences

Coauthor: Gyula Pap

 

Abstract:
Given a digraph D=(V,A) with a designated root node r ∈ V and
arc-costs c:A → R, we consider the problem of finding a minimum
cardinality subset H of the arc set A such that H intersects
every minimum c-cost r-arborescence.
This problem is a special
case of covering minimum cost common bases of two matroids, which is
NP-complete even if the two matroids coincide, and the costs are all
equal to 1.
On the other hand we show that this special case is polynomially
solvable: we give a polynomial algorithm for finding such an arc
set H. The algorithm solves a weighted version as well, in which a
nonnegative weight function w:A → R+ is also given, and we
want to find a subset H of the arc set such that H intersects
every minimum c-cost r-arborescence, and w(H) is minimum.

 

 

Thursday, 15:45 - 16:10 h, Room: H 3012, Talk 2

Mario Leston-Rey
Packing entering sets in kernel systems

Coauthor: Yoshiko Wakabayashi

 

Abstract:
In 1998, H. N. Gabow and K. S. Manu showed a strongly polynomial time
algorithm to obtain - in a capacitated digraph with m arcs and
n edges - a maximum integral packing of at most m + n - 2 arborescences. We extend their result and show that, in the more general framework of packing entering sets in kernel systems, due to A. Frank, an integral packing of size at most m can be computed in strongly polynomial time.

 

 

Thursday, 16:15 - 16:40 h, Room: H 3012, Talk 3

Mikael Call
A polyhedral analysis of a unique shortest path routing polytope

Coauthor: Daniel Karch

 

Abstract:
Consider a strongly connected digraph and two spanning arborescenses. The arborescenses form a unique shortest path system (USPS) if there is a vector of arc costs that simultaneously yields the arborescenses as unique shortest path arborescenses. USPSs correspond to the bases of an independence system. We characterize a large class of facet defining rank inequalities for the associated polytope. In particular, these facets can be obtained by sequential lifting of circuit inequalities. Given a circuit inequality, we determine the facet induced by an arbitrary lifting order.

 

  In particular, Texas Payday Loans can cater to the needs of its residents. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.