$��$-graphic delta-matroids and their applications
| Autor: | Kim, Donggyu, Lee, Duksang, Oum, Sang-il |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| DOI: | 10.48550/arxiv.2104.11383 |
| Popis: | For an abelian group $��$, a $��$-labelled graph is a graph whose vertices are labelled by elements of $��$. We prove that a certain collection of edge sets of a $��$-labelled graph forms a delta-matroid, which we call a $��$-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet to find a maximum weight feasible set in such a delta-matroid. We present two algorithmic applications on graphs; Maximum Weight Packing of Trees of Order Not Divisible by $k$ and Maximum Weight $S$-Tree Packing. We also discuss various properties of $��$-graphic delta-matroids. 16 pages, 2 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|