License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15503/
Go to the corresponding LIPIcs Volume Portal

Kim, Donggyu ; Lee, Duksang ; Oum, Sang-il

Γ-Graphic Delta-Matroids and Their Applications

pdf-format:
LIPIcs-ISAAC-2021-70.pdf (0.7 MB)

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
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI