{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T16:39:12Z","timestamp":1740155952602,"version":"3.37.3"},"reference-count":6,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2019,10]]},"abstract":"<jats:p> We present an algorithm for solving the maximum 1-2 matching problem in bipartite graphs by reducing it to solving the 1-1 matching in general undirected graphs. Further, we propose two variants of the maximum 1-2 matching problem: one is the maximum 1-2 matching problem of the different kind in divided bipartite graphs and the other is the maximum 1-2 matching problem of the same kind in divided bipartite graphs. The former one is shown to be solved by a similar algorithm to that of the maximum 1-2 matching problem by reducing it to solve the maximum 1-1 matching problem in bipartite graphs. For the latter one, we can only present the augmenting subgraph theorem, which is an extension of our augmenting trail theorem for the maximum 1-2 matching problem. <\/jats:p>","DOI":"10.1142\/s1793830919500502","type":"journal-article","created":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T22:20:39Z","timestamp":1564698039000},"page":"1950050","source":"Crossref","is-referenced-by-count":0,"title":["The maximum 1-2 matching problem and two kinds of its variants"],"prefix":"10.1142","volume":"11","author":[{"given":"Hiroki","family":"Izumi","sequence":"first","affiliation":[{"name":"Graduate School of Science and Engineering, Science of Environment and Mathematical Modeling, Doshisha University, 1-3 Tatara Miyakodani, Kyotanabe, Kyoto 610-0394, Japan"}]},{"given":"Yuki","family":"Nishida","sequence":"additional","affiliation":[{"name":"Graduate School of Science and Engineering, Science of Environment and Mathematical Modeling, Doshisha University, 1-3 Tatara Miyakodani, Kyotanabe, Kyoto 610-0394, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3751-5115","authenticated-orcid":false,"given":"Sennosuke","family":"Watanabe","sequence":"additional","affiliation":[{"name":"National Institute of Technology, Oyama College, 771 Nakakuki, Oyama, Tochigi 323-0806, Japan"}]},{"given":"Yoshihide","family":"Watanabe","sequence":"additional","affiliation":[{"name":"Faculty of Science and Engineering, Department of Mathematical Sciences, Doshisha University, 1-3 Tatara Miyakodani, Kyotanabe, Kyoto 610-0394, Japan"}]}],"member":"219","published-online":{"date-parts":[[2019,11,3]]},"reference":[{"volume-title":"Network Flows","year":"1993","author":"Ahuja K.","key":"S1793830919500502BIB001"},{"key":"S1793830919500502BIB002","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.43.9.842"},{"key":"S1793830919500502BIB003","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"S1793830919500502BIB004","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830917500562"},{"key":"S1793830919500502BIB005","volume-title":"Graphs, Networks and Algorithm","author":"Jungnickel D.","year":"2005","edition":"2"},{"key":"S1793830919500502BIB006","volume-title":"Combinatorial Optimization","author":"Korte B.","year":"2001","edition":"2"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830919500502","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T01:14:27Z","timestamp":1572830067000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830919500502"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10]]},"references-count":6,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["10.1142\/S1793830919500502"],"URL":"https:\/\/doi.org\/10.1142\/s1793830919500502","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2019,10]]}}}