LIPIcs.ISAAC.2021.70.pdf
- Filesize: 0.74 MB
- 13 pages
Document
Γ-Graphic Delta-Matroids and Their Applications
Authors
Duksang Lee 
,
Sang-il Oum
-
Part of:
Volume:
32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-11-30
File
Document Identifiers
Author Details
- Department of Mathematical Sciences, KAIST, Daejeon, South Korea
- Discrete Mathematics Group, Institute for Basic Science, Daejeon, South Korea
Cite AsGet BibTex
Donggyu Kim, Duksang Lee, and Sang-il Oum. Γ-Graphic Delta-Matroids and Their Applications. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.70
https://doi.org/10.4230/LIPIcs.ISAAC.2021.70
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Matroids and greedoids
Keywords
- delta-matroid
- group-labelled graph
- greedy algorithm
- tree packing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- André Bouchet. Greedy algorithm and symmetric matroids. Mathematical Programming, 38(2):147-159, 1987. URL: https://doi.org/10.1007/BF02604639.
-
André Bouchet. Representability of △-matroids. In Combinatorics (Eger, 1987), volume 52 of Colloq. Math. Soc. János Bolyai, pages 167-182. North-Holland, Amsterdam, 1988.
- André Bouchet. Maps and △-matroids. Discrete Mathematics, 78(1-2):59-71, 1989. URL: https://doi.org/10.1016/0012-365X(89)90161-1.
- André Bouchet and Alain Duchamp. Representability of △-matroids over GF(2). Linear Algebra Appl., 146:67-78, 1991. URL: https://doi.org/10.1016/0024-3795(91)90020-W.
-
James Ferdinand Geelen. Matchings, matroids and unimodular matrices. ProQuest LLC, Ann Arbor, MI, 1996. Thesis (Ph.D.)-University of Waterloo (Canada).
-
Jiří Matoušek and Jaroslav Nešetřil. Invitation to discrete mathematics. Oxford University Press, Oxford, second edition, 2009.
-
Iain Moffatt. Delta-matroids for graph theorists. In Surveys in combinatorics 2019, volume 456 of London Math. Soc. Lecture Note Ser., pages 167-220. Cambridge Univ. Press, Cambridge, 2019.
- Sang-il Oum. Excluding a bipartite circle graph from line graphs. Journal of Graph Theory, 60(3):183-203, 2009. URL: https://doi.org/10.1002/jgt.20353.
- James Oxley. Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, 2011. URL: https://doi.org/10.1093/acprof:oso/9780198566946.001.0001.
- Frank P. Ramsey. On a problem of formal logic. Proc. London Math. Soc., 30(s2):264-286, 1930. URL: https://doi.org/10.1112/plms/s2-30.1.264.
-
Alan W. Tucker. A combinatorial equivalence of matrices. In Proc. Sympos. Appl. Math., Vol. 10, pages 129-140. American Mathematical Society, Providence, R.I., 1960.