$\Gamma$-graphic delta-matroids and their applications
In: Combinatorica, 43(5):963-983, October 2023; (2021)
Online
report
Zugriff:
For an abelian group $\Gamma$, a $\Gamma$-labelled graph is a graph whose vertices are labelled by elements of $\Gamma$. We prove that a certain collection of edge sets of a $\Gamma$-labelled graph forms a delta-matroid, which we call a $\Gamma$-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 $\Gamma$-graphic delta-matroids.
Comment: 16 pages, 2 figures
Titel: |
$\Gamma$-graphic delta-matroids and their applications
|
---|---|
Autor/in / Beteiligte Person: | Kim, Donggyu ; Lee, Duksang ; Oum, Sang-il |
Link: | |
Quelle: | Combinatorica, 43(5):963-983, October 2023; (2021) |
Veröffentlichung: | 2021 |
Medientyp: | report |
DOI: | 10.1007/s00493-023-00043-6 |
Schlagwort: |
|
Sonstiges: |
|