Hierarchical b-Matching

Basit Öğe Kaydı
dc.authorid0000-0002-3123-3451
dc.authorid0000-0003-2062-6855
dc.authorid0000-0002-2688-5703
dc.contributor.authorEmek, Yuvalen_US
dc.contributor.authorKutten, Shayen_US
dc.contributor.authorShalom, Mordechaien_US
dc.contributor.authorZaks, Shmuelen_US
dc.date.accessioned2021-03-16T09:50:22Z
dc.date.available2021-03-16T09:50:22Z
dc.date.issued2021
dc.departmentIşık Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümüen_US
dc.departmentIşık University, Faculty of Engineering, Department of Computer Engineeringen_US
dc.description.abstractA matching of a graph is a subset of edges no two of which share a common vertex, and a maximum matching is a matching of maximum cardinality. In a b-matching every vertex v has an associated bound bv, and a maximum b-matching is a maximum set of edges, such that every vertex v appears in at most bv of them. We study an extension of this problem, termed Hierarchical b-Matching. In this extension, the vertices are arranged in a hierarchical manner. At the first level the vertices are partitioned into disjoint subsets, with a given bound for each subset. At the second level the set of these subsets is again partitioned into disjoint subsets, with a given bound for each subset, and so on. We seek for a maximum set of edges, that obey all bounds (that is, no vertex v participates in more than bv edges, then all the vertices in one subset do not participate in more that subset’s bound of edges, and so on hierarchically). This is a sub-problem of the matroid matching problem which is NP -hard in general. It corresponds to the special case where the matroid is restricted to be laminar and the weights are unity. A pseudo-polynomial algorithm for the weighted laminar matroid matching problem is presented in [8]. We propose a polynomial-time algorithm for Hierarchical b-matching, i.e. the unweighted laminar matroid matching problem, and discuss how our techniques can possibly be generalized to the weighted case.en_US
dc.description.versionPublisher's Versionen_US
dc.identifier.citationEmek, Y., Kutten, S., Shalom, M. & Zaks, S. (2021). Hierarchical b-Matching. Paper presented at the Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12607, 189-202. doi:10.1007/978-3-030-67731-2_14en_US
dc.identifier.doi10.1007/978-3-030-67731-2_14
dc.identifier.endpage202
dc.identifier.isbn9783030677305
dc.identifier.isbn9783030677312
dc.identifier.issn0302-9743
dc.identifier.issn1611-3349
dc.identifier.scopus2-s2.0-85101552365
dc.identifier.scopusqualityQ3
dc.identifier.startpage189
dc.identifier.urihttps://hdl.handle.net/11729/3099
dc.identifier.urihttp://dx.doi.org/10.1007/978-3-030-67731-2_14
dc.identifier.volume12607
dc.identifier.wosWOS:000927597000014
dc.identifier.wosqualityQ4
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakConference Proceedings Citation Index – Science (CPCI-S)en_US
dc.institutionauthorShalom, Mordechaien_US
dc.institutionauthorid0000-0002-2688-5703
dc.language.isoenen_US
dc.peerreviewedYesen_US
dc.publicationstatusPublisheden_US
dc.publisherSpringer Science and Business Media Deutschland GmbHen_US
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectb-matchingen_US
dc.subjectMatchingen_US
dc.subjectMatroidsen_US
dc.subjectCombinatorial mathematicsen_US
dc.subjectNP-harden_US
dc.subjectPolynomial approximationen_US
dc.subjectCardinalitiesen_US
dc.subjectDisjoint subsetsen_US
dc.subjectMatching problemsen_US
dc.subjectMaximum matchingsen_US
dc.subjectPolynomial-time algorithmsen_US
dc.subjectPseudopolynomial algorithmsen_US
dc.subjectSecond levelen_US
dc.subjectSub-problemsen_US
dc.subjectSet theoryen_US
dc.titleHierarchical b-Matchingen_US
dc.typeConference Objecten_US
dspace.entity.typePublication

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
Ä°sim:
3099.pdf
Boyut:
446.41 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Publisher's Version
Ä°ndir
Lisans paketi
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
Ä°sim:
license.txt
Boyut:
1.44 KB
Biçim:
Item-specific license agreed upon to submission
Açıklama:
Ä°ndir

Koleksiyon

Scopus İndeksli Yayınlar Koleksiyonu
Bildiri Koleksiyonu | Bilgisayar Mühendisliği Bölümü
WoS İndeksli Yayınlar Koleksiyonu