BROWSE

Related Scientist

's photo.

수리및계산과학연구단
more info

ITEM VIEW & DOWNLOAD

G-Graphic Delta-Matroids and Their Applications

Cited 0 time in webofscience Cited 0 time in scopus
83 Viewed 0 Downloaded
Title
G-Graphic Delta-Matroids and Their Applications
Author(s)
Donggyu Kim; Duksang Lee; Sang-il Oum
Publication Date
2023-10
Journal
Combinatorica, v.43, no.5, pp.963 - 983
Publisher
Springer Verlag
Abstract
For an abelian group G, a G-labelled graph is a graph whose vertices are labelled by elements of G. We prove that a certain collection of edge sets of a G-labelled graph forms a delta-matroid, which we call a G -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 G-graphic deltamatroids.
URI
https://pr.ibs.re.kr/handle/8788114/14631
DOI
10.1007/s00493-023-00043-6
ISSN
0209-9683
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse