E
and a subset of its
d
-element subsets, these form the bases of a matroid
if and only if they satisfy the Steinitz exchange axiom of linear
algebra
IfMatroids arise not only from points in vector spaces but also from graphs, transversal systems, matchable sets and many others.B1, B2
are bases ande
is an element inB1\B2
, then there exists an elementf
inB2\B1
such thatB1 - e + f
is a basis again.
Among others we examined the structure of the set of circuits in binary matroids (with Jackson B: Large Circuits in Binary Matroids of Large Cogirth: I. andII.), (with Nešetřil J: A Note on MaxFlow-MinCut and Homomorphic Equivalence in Matroids). Also we discovered them in a problem motivated by a real world application (with Epping T, Lübecke M E: Max-Flow Min-Cut Duality for a Paint Shop Problem).
Recently we considered generalizations of flows in digraphs to oriented matroids (with Goddyn L, Hlineny P: Balanced Signings of Oriented Matroids and Chromatic Number), (with Nickel R: The Flow Lattice of Oriented Matroids).
S
that can form coalitions K
. Such a coalition receives
a payment v(K)
. One of the main issues of cooperative
game theory is to determine solution concepts, i.e. how to allocate
the money to the players in the coalition. Of particular interest
are allocations of v(S)
, the value of the grand
coalition of all players, with the property that no coalition has
an incentive to split from the grand coalition. We call such a
solution stable.
Our main focus is the computational complexity of solution concepts of games where the payoff of a coalition is defined by some problem from combinatorial optimization, such as matching or travelling salesman (with Faigle U, Fekete S, Kern W: On the Complexity of Testing Membership in the Core of Min-cost Spanning Tree Games), (with Faigle U, Kern W, Fekete S: The Nukleon of Cooperative Games and an Algorithm for Matching Games), (with Jin H, Nickel R: The Hungarian Method for a Mixed Matching Market).
k
colors feasibly. If in the end the graph is
completely colored the maker wins. The breaker aims at enforcing a
blocking situation where there are uncolored elements that cannot
be feasibly colored without introducing an extra color.
We examine how many colors are necessary in certain graph
classes such that the maker always has a winning strategy (with Erdös P, Faigle U, Kern W:
Note on the Game Chromatic Index of Trees).
Learn more about coloring games at our homepage of Graph Coloring Games.
P4
NP
-complete in general
can be solved efficiently or even in linear time. This property is
invariant if only few P4
are present (with Tinhofer G: Hamiltonicity in Graphs
with few P4s). Also matrix partition problems can be
efficiently solved on cographs (with Feder
T, Hell P: Generalized Colorings (Matrix Partitions) of
Cographs).
This is the first non-trivial class of graphs where these general coloring problems are easy.
Starting from the problem to reduce the number of color changes in the paint shop (with Epping T, Oertel P: Complexity Results on a Paint Shop Problem), we developed a new algorithm to do the full sequencing. An implementation of our method is used in plants all over Europe (with Epping T, Nickel R, Oertel P: Order Sequencing in the Automobile Industry).
We developed several heuristics for that purpose (with Bachem A, Malich M: The Simulated Trading Heuristic for Solving Vehicle Routing Problems), (with Hamacher A, Moll C: Tree Partitioning under Constraints – Clustering for Vehicle Routing Problems). One of our methods is used for the strategic planning of the distribution of newspapers.
© FernUniversität in Hagen – Discrete Mathematics and
Optimization
webdesign and programming: Heidrun Krimmel,
Cologne