کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420063 | 683891 | 2007 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Induction of M-convex functions by linking systems Induction of M-convex functions by linking systems](/preview/png/420063.png)
Induction (or transformation) by bipartite graphs is one of the most important operations on matroids, and it is well known that the induction of a matroid by a bipartite graph is again a matroid. As an abstract form of this fact, the induction of a matroid by a linking system is known to be a matroid.M-convex functions are quantitative extensions of matroidal structures, and they are known as discrete convex functions. As with matroids, it is known that the induction of an M-convex function by networks generates an M-convex function. As an abstract form of this fact, this paper shows that the induction of an M-convex function by linking systems generates an M-convex function. Furthermore, we show that this result also holds for M-convex functions on constant-parity jump systems. Previously known operations such as aggregation, splitting, and induction by networks can be understood as special cases of this construction.
Journal: Discrete Applied Mathematics - Volume 155, Issue 11, 1 June 2007, Pages 1471–1480