BROWSE

Related Scientist

's photo.

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

ITEM VIEW & DOWNLOAD

Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k

DC Field Value Language
dc.contributor.authorKanté, M.M.-
dc.contributor.authorKim, E.J.-
dc.contributor.authorO-joung Kwon-
dc.contributor.authorSang-il Oum-
dc.date.accessioned2023-04-10T22:00:13Z-
dc.date.available2023-04-10T22:00:13Z-
dc.date.created2023-03-06-
dc.date.issued2023-05-
dc.identifier.issn0095-8956-
dc.identifier.urihttps://pr.ibs.re.kr/handle/8788114/13213-
dc.description.abstractEvery minor-closed class of matroids of bounded branch-width can be characterized by a list of excluded minors, but unlike graphs, this list may need to be infinite in general. However, for each fixed finite field F, the list needs to contain only finitely many F-representable matroids, due to the well-quasi-ordering of F-representable matroids of bounded branch-width under taking matroid minors [J.F. Geelen, A.M.H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these F-representable excluded minors in general. We consider the class of matroids of path-width at most k for fixed k. We prove that for a finite field F, every F-representable excluded minor for the class of matroids of path-width at most k has at most 2|F|O(k2) elements. We can therefore compute, for any integer k and a fixed finite field F, the set of F-representable excluded minors for the class of matroids of path-width k, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an F-represented matroid is at most k. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most k has at most 22O(k2) vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs. © 2022 Elsevier Inc.-
dc.language영어-
dc.publisherAcademic Press Inc.-
dc.titleObstructions for matroids of path-width at most k and graphs of linear rank-width at most k-
dc.typeArticle-
dc.type.rimsART-
dc.identifier.wosid001003649800001-
dc.identifier.scopusid2-s2.0-85146690042-
dc.identifier.rimsid80058-
dc.contributor.affiliatedAuthorO-joung Kwon-
dc.contributor.affiliatedAuthorSang-il Oum-
dc.identifier.doi10.1016/j.jctb.2022.12.004-
dc.identifier.bibliographicCitationJournal of Combinatorial Theory. Series B, v.160, pp.15 - 35-
dc.relation.isPartOfJournal of Combinatorial Theory. Series B-
dc.citation.titleJournal of Combinatorial Theory. Series B-
dc.citation.volume160-
dc.citation.startPage15-
dc.citation.endPage35-
dc.type.docTypeArticle-
dc.description.journalClass1-
dc.description.journalClass1-
dc.description.isOpenAccessN-
dc.description.journalRegisteredClassscie-
dc.description.journalRegisteredClassscopus-
dc.relation.journalResearchAreaMathematics-
dc.relation.journalWebOfScienceCategoryMathematics-
dc.subject.keywordPlusMONADIC 2ND-ORDER LOGIC-
dc.subject.keywordPlusVERTEX-MINORS-
dc.subject.keywordPlusBRANCH-WIDTH-
dc.subject.keywordAuthorForbidden minor-
dc.subject.keywordAuthorGraph-
dc.subject.keywordAuthorLinear rank-width-
dc.subject.keywordAuthorMatroid-
dc.subject.keywordAuthorPath-width-
dc.subject.keywordAuthorPivot-minor-
dc.subject.keywordAuthorVertex-minor-
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