Eand 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, B2are bases and
B1\B2, then there exists an element
B1 - e + fis 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).
Sthat 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).
kcolors 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.
NP-complete in general can be solved efficiently or even in linear time. This property is invariant if only few
P4are 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
webdesign and programming: Heidrun Krimmel, Cologne