1 Ocak 2013 Dergi makalesi Açık Erişim

Bodur, Merve; Ekim, Tinaz; Taskin, Z. Caner

MARC21 XML

<?xml version='1.0' encoding='UTF-8'?>
<record xmlns="http://www.loc.gov/MARC21/slim">
  <leader>00000nam##2200000uu#4500</leader>
  <datafield tag="909" ind1="C" ind2="O">
    <subfield code="p">user-tubitak-destekli-proje-yayinlari</subfield>
    <subfield code="o">oai:zenodo.org:15359</subfield>
  </datafield>
  <datafield tag="520" ind1=" " ind2=" ">
    <subfield code="a">- We investigate the problem of finding a maximal matching that has minimum total weight on a given edge-weighted graph. Although the minimum weight maximal matching problem is NP-hard in general, polynomial time exact or approximation algorithms on several restricted graph classes are given in the literature. In this article, we propose an exact algorithm for solving several variants of the problem on general graphs. In particular, we develop integer programming (IP) formulations for the problem and devise a decomposition algorithm, which is based on a combination of IP techniques and combinatorial matching algorithms. Our computational tests on a large suite of randomly generated graphs show that our decomposition approach significantly improves the solvability of the problem compared to the underlying IP formulation. (c) 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 62(4), 273-287 2013</subfield>
  </datafield>
  <datafield tag="980" ind1=" " ind2=" ">
    <subfield code="a">publication</subfield>
    <subfield code="b">article</subfield>
  </datafield>
  <datafield tag="540" ind1=" " ind2=" ">
    <subfield code="a">Creative Commons Attribution</subfield>
    <subfield code="u">http://www.opendefinition.org/licenses/cc-by</subfield>
  </datafield>
  <datafield tag="100" ind1=" " ind2=" ">
    <subfield code="a">Bodur, Merve</subfield>
    <subfield code="u">Bogazici Univ, Dept Ind Engn, TR-34342 Istanbul, Turkey</subfield>
  </datafield>
  <datafield tag="856" ind1="4" ind2=" ">
    <subfield code="z">md5:7c6449a2a902ea87f20fa03daed7389f</subfield>
    <subfield code="s">148</subfield>
    <subfield code="u">https://aperta.ulakbim.gov.trrecord/15359/files/bib-8e7a0cf8-3793-4d7d-813a-b80a34b80224.txt</subfield>
  </datafield>
  <controlfield tag="005">20210315083334.0</controlfield>
  <datafield tag="260" ind1=" " ind2=" ">
    <subfield code="c">2013-01-01</subfield>
  </datafield>
  <datafield tag="024" ind1=" " ind2=" ">
    <subfield code="a">10.1002/net.21516</subfield>
    <subfield code="2">doi</subfield>
  </datafield>
  <datafield tag="542" ind1=" " ind2=" ">
    <subfield code="l">open</subfield>
  </datafield>
  <datafield tag="245" ind1=" " ind2=" ">
    <subfield code="a">Decomposition Algorithms for Solving the Minimum Weight Maximal Matching Problem</subfield>
  </datafield>
  <datafield tag="909" ind1="C" ind2="4">
    <subfield code="v">62</subfield>
    <subfield code="p">NETWORKS</subfield>
    <subfield code="c">273-287</subfield>
    <subfield code="n">4</subfield>
  </datafield>
  <datafield tag="650" ind1="1" ind2="7">
    <subfield code="a">cc-by</subfield>
    <subfield code="2">opendefinition.org</subfield>
  </datafield>
  <datafield tag="700" ind1=" " ind2=" ">
    <subfield code="a">Ekim, Tinaz</subfield>
    <subfield code="u">Bogazici Univ, Dept Ind Engn, TR-34342 Istanbul, Turkey</subfield>
  </datafield>
  <datafield tag="700" ind1=" " ind2=" ">
    <subfield code="a">Taskin, Z. Caner</subfield>
    <subfield code="u">Bogazici Univ, Dept Ind Engn, TR-34342 Istanbul, Turkey</subfield>
  </datafield>
  <controlfield tag="001">15359</controlfield>
  <datafield tag="980" ind1=" " ind2=" ">
    <subfield code="a">user-tubitak-destekli-proje-yayinlari</subfield>
  </datafield>
</record>