Contributed Session Thu.3.H 3012

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

Cluster 2: Combinatorial optimization [...]



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


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


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


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. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Buy Cialis is the one that definitely differs from all other products.