Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.70
URN: urn:nbn:de:0030-drops-155038
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15503/
Kim, Donggyu ; Lee, Duksang ; Oum, Sang-il
Γ-Graphic Delta-Matroids and Their Applications
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{kim_et_al:LIPIcs.ISAAC.2021.70,
author = {Kim, Donggyu and Lee, Duksang and Oum, Sang-il},
title = {{\Gamma-Graphic Delta-Matroids and Their Applications}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {70:1--70:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15503},
URN = {urn:nbn:de:0030-drops-155038},
doi = {10.4230/LIPIcs.ISAAC.2021.70},
annote = {Keywords: delta-matroid, group-labelled graph, greedy algorithm, tree packing}
}
| Keywords: | delta-matroid, group-labelled graph, greedy algorithm, tree packing | |
| Seminar: | 32nd International Symposium on Algorithms and Computation (ISAAC 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 30.11.2021 |
