{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T11:43:29Z","timestamp":1697888609736},"reference-count":19,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8350,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Consider a directed graph <jats:italic>G<\/jats:italic> in which every edge has an associated real\u2010valued distance and a real\u2010valued weight. The weight of an undirected circuit of <jats:italic>G<\/jats:italic> is the sum of the weights of the edges, whereas the distance of an undirected circuit is the sum of the distances of the forward edges of the circuit minus the sum of the distances of the backward edges. A trivial circuit is a two\u2010edge circuit in which one edge of <jats:italic>G<\/jats:italic> appears twice on the circuit. A quasidynamic fractional matching (or <jats:italic>Q<\/jats:italic>\u2010matching) is a collection of vertex\u2010disjoint circuits such that each circuit is either trivial or else it is an odd circuit whose distance is nonzero. The <jats:italic>G<\/jats:italic>\u2010matching problem is to find a <jats:italic>Q<\/jats:italic>\u2010matching that maximizes the sum of the weights of its circuits. The <jats:italic>Q<\/jats:italic>\u2010matching problem generalizes both the matching problem and the fractional matching problem. Moreover, the dynamic matching problem, which is a matching problem on an infinite dynamic (time\u2010expanded) graph, is linearly transformable to the <jats:italic>Q<\/jats:italic>\u2010matching problem, as shown in Part I of this paper. In this paper we solve the <jats:italic>Q<\/jats:italic>\u2010matching problem by generalizing Edmonds' blossom algorithm. In fact, all of the major components of the blossom algorithm\u2010including alternating trees, augmentations, shrinking, and expanding\u2010are appropriately generalized to yield a running time that is proportional to that for the weighted matching problem. Furthermore, if all edge distances are equal to zero, this new algorithm reduces to the blossom algorithm.<\/jats:p>","DOI":"10.1002\/net.3230130408","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T17:17:57Z","timestamp":1178903877000},"page":"563-580","source":"Crossref","is-referenced-by-count":2,"title":["Dynamic matchings and quasidynamic fractional matchings. II"],"prefix":"10.1002","volume":"13","author":[{"given":"James B.","family":"Orlin","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.43.9.842"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90016-5"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90002-3"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120901"},{"key":"e_1_2_1_6_2","unstructured":"G.CornuejolsandW.Pulleyblank Critical graphs matchings and tours or a hierarchy of relaxations for the travelling salesman problem. Technical Report No. 81198\u2013OR Institut fur Okonometrie and Operations Research Reinische Fried\u2010rich\u2010Wilhelms\u2010Universit\u00e4t Bonn West Germany (1981)."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121194"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_10_2","unstructured":"J.Edmonds E.Johnson andS..Lockhart Blossom I a code for matching. Unpublished Report IBM Research Center Yorktown Heights NY (1969)."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.5"},{"key":"e_1_2_1_12_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M.","year":"1979"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_14_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E.","year":"1976"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130407"},{"key":"e_1_2_1_16_2","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C.","year":"1982"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"W.Pulleyblank Facets of matching polyhedra. Ph.D. Thesis. University of Waterloo 1973","DOI":"10.1007\/BFb0066196"},{"key":"e_1_2_1_18_2","unstructured":"W.Pulleyblank Dual integrality inb\u2010matching problems. CORE Discussion Paper Louvain Belgium (1977)."},{"key":"e_1_2_1_19_2","volume-title":"Hypergraph Seminar, Lecture Notes in Mathematics","author":"Pulleyblank W.","year":"1974"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-22.2.107"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130408","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T02:59:07Z","timestamp":1697770747000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130408"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,12]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1983,12]]}},"alternative-id":["10.1002\/net.3230130408"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130408","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,12]]}}}