Hierarchical b-Matching
Künye
Emek, 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_14Özet
A 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.
Kaynak
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Cilt
12607Aşağıdaki lisans dosyası bu öğe ile ilişkilidir:
İlgili Öğeler
Başlık, yazar, küratör ve konuya göre gösterilen ilgili öğeler.
-
A tunable inductance topology to realize frequency tunable matching networks and amplifiers
Atilla, Doğu Çağdaş; Aydın, Çağatay; Köprü, Ramazan; Nesimoğlu, Tayfun; Yarman, Bekir Sıddık Binboğa (IEEE, 2013)Coverage of commercial communication standards such as GSM, UMTS, Wi-Fi and Wi-Max within a single transceiver chip is one of the most desired properties by wireless communication manufacturers. In this regard, communication ... -
Transformerless bandpass matching network design for Y-Shaped monopole antenna
Aydın, Çağatay; Atilla, Doğu Çağdaş; Karakuş, Cahit; Köprü, Ramazan; Yarman, Bekir Sıddık Binboğa (IEEE, 2015)In this paper, a transformerless bandpass matching network design procedure is presented. The Real Frequency Techniques are powerful numerical methods to design wideband lossless 2-port networks such that filters and ... -
Design and realization of wideband matching networks in Richards domain
Köprü, Ramazan; Kılınç, Sedat; Yarman, Bekir Sıddık Binboğa (Institute of Electrical and Electronics Engineers Inc, 2014)A broadband matching network design is given with its simulation and prototype measurement results. The circuit contains certain number of cascaded unit-elements (UEs) and open-stubs which behave as Richards capacitors. ...