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.

 

  Payday Loans In Florida. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.