Node-weighted graphs having the König-Egerváry property View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009-02-26

AUTHORS

J. -M. Bourjolly , P. L. Hammer , B. Simeone

ABSTRACT

A graph G with positive integral node-weights bi is said to be a b-König-Egerváry graph (b-KEG for short) if there exist a transversal T and a b-matching λ such that the weight of T is equal to the value of λ; the usual König-Egerváry graphs correspond to b=(1, 1, …, 1). Several characterizations and two polynomial recognition algorithms for b-KEGs are presented. Algorithm 1 either recognizes (G, b) as being a b-KEG, or else exhibits an ‘obstruction’. Algorithm 2 associates a quadratic boolean function f with (G, b) and reduces the problem of recognizing whether (G, b) is a b-KEG to that of solving the equation f=0. In case (G, b) is a b-KEG, both algorithms provide a minimum weight transversal. Some of our results generalize previous results obtained in the unweighted case by Deming, Gavril and Sterboul. A companion paper will analyze applications of the weighted König-Egerváry property to quadratic 0–1 optimization. More... »

PAGES

44-63

References to SciGraph publications

  • 2009-02-24. Dual integrality in b-matching problems in COMBINATORIAL OPTIMIZATION
  • Book

    TITLE

    Mathematical Programming at Oberwolfach II

    ISBN

    978-3-642-00914-3
    978-3-642-00915-0

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bfb0121007

    DOI

    http://dx.doi.org/10.1007/bfb0121007

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1021402555


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "University of Waterloo, Ontario, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bourjolly", 
            "givenName": "J. -M.", 
            "id": "sg:person.01345361242.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01345361242.70"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Rutgers University", 
              "id": "https://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Rutgers University, New Brunswick, NJ, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hammer", 
            "givenName": "P. L.", 
            "id": "sg:person.015740461177.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015740461177.00"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "University of Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Simeone", 
            "givenName": "B.", 
            "id": "sg:person.012600006066.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0020-0190(78)90016-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010516092"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(77)90068-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015721120"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(79)90002-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023830880"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(79)90066-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027241407"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0095-8956(79)90085-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034128615"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0120895", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047880308", 
              "https://doi.org/10.1007/bfb0120895"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0120895", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047880308", 
              "https://doi.org/10.1007/bfb0120895"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0603052", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062848777"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4153/cjm-1954-033-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072263933"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2009-02-26", 
        "datePublishedReg": "2009-02-26", 
        "description": "A graph G with positive integral node-weights bi is said to be a b-K\u00f6nig-Egerv\u00e1ry graph (b-KEG for short) if there exist a transversal T and a b-matching \u03bb such that the weight of T is equal to the value of \u03bb; the usual K\u00f6nig-Egerv\u00e1ry graphs correspond to b=(1, 1, \u2026, 1). Several characterizations and two polynomial recognition algorithms for b-KEGs are presented. Algorithm 1 either recognizes (G, b) as being a b-KEG, or else exhibits an \u2018obstruction\u2019. Algorithm 2 associates a quadratic boolean function f with (G, b) and reduces the problem of recognizing whether (G, b) is a b-KEG to that of solving the equation f=0. In case (G, b) is a b-KEG, both algorithms provide a minimum weight transversal. Some of our results generalize previous results obtained in the unweighted case by Deming, Gavril and Sterboul. A companion paper will analyze applications of the weighted K\u00f6nig-Egerv\u00e1ry property to quadratic 0\u20131 optimization.", 
        "editor": [
          {
            "familyName": "Korte", 
            "givenName": "Bernhard", 
            "type": "Person"
          }, 
          {
            "familyName": "Ritter", 
            "givenName": "Klaus", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/bfb0121007", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-00914-3", 
            "978-3-642-00915-0"
          ], 
          "name": "Mathematical Programming at Oberwolfach II", 
          "type": "Book"
        }, 
        "name": "Node-weighted graphs having the K\u00f6nig-Egerv\u00e1ry property", 
        "pagination": "44-63", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1021402555"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bfb0121007"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "65f8cc96fe9c625f092e84fdfb898255b13302fe73e659f7cab570377215f71e"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/bfb0121007", 
          "https://app.dimensions.ai/details/publication/pub.1021402555"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:04", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000352_0000000352/records_60366_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2FBFb0121007"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bfb0121007'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bfb0121007'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0121007'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0121007'


     

    This table displays all metadata directly associated to this object as RDF triples.

    115 TRIPLES      23 PREDICATES      34 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bfb0121007 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N440cc49a4cae4a4391efa85e9dc45eaf
    4 schema:citation sg:pub.10.1007/bfb0120895
    5 https://doi.org/10.1016/0012-365x(79)90066-9
    6 https://doi.org/10.1016/0020-0190(77)90068-0
    7 https://doi.org/10.1016/0020-0190(78)90016-9
    8 https://doi.org/10.1016/0020-0190(79)90002-4
    9 https://doi.org/10.1016/0095-8956(79)90085-6
    10 https://doi.org/10.1137/0603052
    11 https://doi.org/10.4153/cjm-1954-033-3
    12 schema:datePublished 2009-02-26
    13 schema:datePublishedReg 2009-02-26
    14 schema:description A graph G with positive integral node-weights bi is said to be a b-König-Egerváry graph (b-KEG for short) if there exist a transversal T and a b-matching λ such that the weight of T is equal to the value of λ; the usual König-Egerváry graphs correspond to b=(1, 1, …, 1). Several characterizations and two polynomial recognition algorithms for b-KEGs are presented. Algorithm 1 either recognizes (G, b) as being a b-KEG, or else exhibits an ‘obstruction’. Algorithm 2 associates a quadratic boolean function f with (G, b) and reduces the problem of recognizing whether (G, b) is a b-KEG to that of solving the equation f=0. In case (G, b) is a b-KEG, both algorithms provide a minimum weight transversal. Some of our results generalize previous results obtained in the unweighted case by Deming, Gavril and Sterboul. A companion paper will analyze applications of the weighted König-Egerváry property to quadratic 0–1 optimization.
    15 schema:editor N1ce18f24bac045bcbb701f9a5e694e7c
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf Nbdcf409c3f7a47a7a982f5af75b6a9ba
    20 schema:name Node-weighted graphs having the König-Egerváry property
    21 schema:pagination 44-63
    22 schema:productId Nd899b423734644b5bb81688fc5837bac
    23 Nf2b75ce4b7af4f68b462126f5b9821e3
    24 Nfe80a3da848b46f084f76bb6c1697d48
    25 schema:publisher N4bc69fd936a545edb50296920bd75644
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021402555
    27 https://doi.org/10.1007/bfb0121007
    28 schema:sdDatePublished 2019-04-16T07:04
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher Nd6824cd268ea4e0e958e5b64bf29d750
    31 schema:url https://link.springer.com/10.1007%2FBFb0121007
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N1ce18f24bac045bcbb701f9a5e694e7c rdf:first N8d7d3484380845268f25a6344177b44a
    36 rdf:rest N82216f6061bb4dd48e7de51a1d70a355
    37 N440cc49a4cae4a4391efa85e9dc45eaf rdf:first sg:person.01345361242.70
    38 rdf:rest N9157d480d77e4d7bad88e0cd8745637d
    39 N4bc69fd936a545edb50296920bd75644 schema:location Berlin, Heidelberg
    40 schema:name Springer Berlin Heidelberg
    41 rdf:type schema:Organisation
    42 N82216f6061bb4dd48e7de51a1d70a355 rdf:first N8cbcfc8536b54315a16a59525b3c9ec9
    43 rdf:rest rdf:nil
    44 N8cbcfc8536b54315a16a59525b3c9ec9 schema:familyName Ritter
    45 schema:givenName Klaus
    46 rdf:type schema:Person
    47 N8d7d3484380845268f25a6344177b44a schema:familyName Korte
    48 schema:givenName Bernhard
    49 rdf:type schema:Person
    50 N9157d480d77e4d7bad88e0cd8745637d rdf:first sg:person.015740461177.00
    51 rdf:rest Ndf78da7c10e742c0947706b30597d68f
    52 Nbdcf409c3f7a47a7a982f5af75b6a9ba schema:isbn 978-3-642-00914-3
    53 978-3-642-00915-0
    54 schema:name Mathematical Programming at Oberwolfach II
    55 rdf:type schema:Book
    56 Nd6824cd268ea4e0e958e5b64bf29d750 schema:name Springer Nature - SN SciGraph project
    57 rdf:type schema:Organization
    58 Nd899b423734644b5bb81688fc5837bac schema:name dimensions_id
    59 schema:value pub.1021402555
    60 rdf:type schema:PropertyValue
    61 Ndf78da7c10e742c0947706b30597d68f rdf:first sg:person.012600006066.78
    62 rdf:rest rdf:nil
    63 Nf2b75ce4b7af4f68b462126f5b9821e3 schema:name readcube_id
    64 schema:value 65f8cc96fe9c625f092e84fdfb898255b13302fe73e659f7cab570377215f71e
    65 rdf:type schema:PropertyValue
    66 Nfe80a3da848b46f084f76bb6c1697d48 schema:name doi
    67 schema:value 10.1007/bfb0121007
    68 rdf:type schema:PropertyValue
    69 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Information and Computing Sciences
    71 rdf:type schema:DefinedTerm
    72 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Computation Theory and Mathematics
    74 rdf:type schema:DefinedTerm
    75 sg:person.012600006066.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    76 schema:familyName Simeone
    77 schema:givenName B.
    78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
    79 rdf:type schema:Person
    80 sg:person.01345361242.70 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    81 schema:familyName Bourjolly
    82 schema:givenName J. -M.
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01345361242.70
    84 rdf:type schema:Person
    85 sg:person.015740461177.00 schema:affiliation https://www.grid.ac/institutes/grid.430387.b
    86 schema:familyName Hammer
    87 schema:givenName P. L.
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015740461177.00
    89 rdf:type schema:Person
    90 sg:pub.10.1007/bfb0120895 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047880308
    91 https://doi.org/10.1007/bfb0120895
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1016/0012-365x(79)90066-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027241407
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1016/0020-0190(77)90068-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015721120
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/0020-0190(78)90016-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010516092
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/0020-0190(79)90002-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023830880
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/0095-8956(79)90085-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034128615
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1137/0603052 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848777
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.4153/cjm-1954-033-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072263933
    106 rdf:type schema:CreativeWork
    107 https://www.grid.ac/institutes/grid.430387.b schema:alternateName Rutgers University
    108 schema:name Rutgers University, New Brunswick, NJ, USA
    109 rdf:type schema:Organization
    110 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
    111 schema:name University of Waterloo, Ontario, Canada
    112 rdf:type schema:Organization
    113 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    114 schema:name University of Rome, Italy
    115 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...