On NP-Hardness in Hierarchical Clustering View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1984

AUTHORS

M. Křivánek , J. Morávek

ABSTRACT

We consider a class of optimization problems of the hierarchical-tree clustering, and prove that these problems are NP-hard. The sequence of polynomial reductions and/or transformations used in our proof is based on graph-theoretical techniques and constructions, and starts in the NP-complete problem of 5-dimensional matching.

PAGES

189-194

References to SciGraph publications

  • 1967-09. Hierarchical clustering schemes in PSYCHOMETRIKA
  • Book

    TITLE

    Compstat 1984

    ISBN

    978-3-7051-0007-7
    978-3-642-51883-6

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-51883-6_26

    DOI

    http://dx.doi.org/10.1007/978-3-642-51883-6_26

    DIMENSIONS

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


    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": [
          {
            "familyName": "K\u0159iv\u00e1nek", 
            "givenName": "M.", 
            "id": "sg:person.015424541177.36", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015424541177.36"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Praha, Czech Republic"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mor\u00e1vek", 
            "givenName": "J.", 
            "id": "sg:person.015242762255.88", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015242762255.88"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02289588", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041776510", 
              "https://doi.org/10.1007/bf02289588"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02289588", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041776510", 
              "https://doi.org/10.1007/bf02289588"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/biomet/58.1.91", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059418004"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1984", 
        "datePublishedReg": "1984-01-01", 
        "description": "We consider a class of optimization problems of the hierarchical-tree clustering, and prove that these problems are NP-hard. The sequence of polynomial reductions and/or transformations used in our proof is based on graph-theoretical techniques and constructions, and starts in the NP-complete problem of 5-dimensional matching.", 
        "editor": [
          {
            "familyName": "Havr\u00e1nek", 
            "givenName": "T.", 
            "type": "Person"
          }, 
          {
            "familyName": "\u0160id\u00e1k", 
            "givenName": "Z.", 
            "type": "Person"
          }, 
          {
            "familyName": "Nov\u00e1k", 
            "givenName": "M.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-51883-6_26", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-7051-0007-7", 
            "978-3-642-51883-6"
          ], 
          "name": "Compstat 1984", 
          "type": "Book"
        }, 
        "name": "On NP-Hardness in Hierarchical Clustering", 
        "pagination": "189-194", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-51883-6_26"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e24fe362450239badf4370cec55827a43d638bf3dd1cfa39dfb016ff2f937c85"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1047507966"
            ]
          }
        ], 
        "publisher": {
          "location": "Heidelberg", 
          "name": "Physica-Verlag HD", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-51883-6_26", 
          "https://app.dimensions.ai/details/publication/pub.1047507966"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T11:37", 
        "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/0000000001_0000000264/records_8660_00000272.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-51883-6_26"
      }
    ]
     

    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/978-3-642-51883-6_26'

    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/978-3-642-51883-6_26'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-51883-6_26'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-51883-6_26'


     

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

    87 TRIPLES      23 PREDICATES      29 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-51883-6_26 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nb455104c6ae34219aab4abe574b48f35
    4 schema:citation sg:pub.10.1007/bf02289588
    5 https://doi.org/10.1093/biomet/58.1.91
    6 schema:datePublished 1984
    7 schema:datePublishedReg 1984-01-01
    8 schema:description We consider a class of optimization problems of the hierarchical-tree clustering, and prove that these problems are NP-hard. The sequence of polynomial reductions and/or transformations used in our proof is based on graph-theoretical techniques and constructions, and starts in the NP-complete problem of 5-dimensional matching.
    9 schema:editor N1e5ba97d661d49479b546059b3a19654
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N3b1d582d48d54e698bfbe933e75bcddc
    14 schema:name On NP-Hardness in Hierarchical Clustering
    15 schema:pagination 189-194
    16 schema:productId N5af98a3424ec46338ab32d0ff3afb580
    17 Ndc691f09dde545baa52d58dddf017df0
    18 Nf3af2cc1312a4bbdbd4ba381b386ae67
    19 schema:publisher N2fbbab6ebb60494789b38a517618e674
    20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047507966
    21 https://doi.org/10.1007/978-3-642-51883-6_26
    22 schema:sdDatePublished 2019-04-15T11:37
    23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    24 schema:sdPublisher Nc01b77e409404b99b746eaf8058c8ea1
    25 schema:url http://link.springer.com/10.1007/978-3-642-51883-6_26
    26 sgo:license sg:explorer/license/
    27 sgo:sdDataset chapters
    28 rdf:type schema:Chapter
    29 N1e5ba97d661d49479b546059b3a19654 rdf:first Ne54a2ab912184937aa0c7b0b76a6c09d
    30 rdf:rest N3c923e30167b4c2695accf5b310ca765
    31 N2fbbab6ebb60494789b38a517618e674 schema:location Heidelberg
    32 schema:name Physica-Verlag HD
    33 rdf:type schema:Organisation
    34 N3b1d582d48d54e698bfbe933e75bcddc schema:isbn 978-3-642-51883-6
    35 978-3-7051-0007-7
    36 schema:name Compstat 1984
    37 rdf:type schema:Book
    38 N3c923e30167b4c2695accf5b310ca765 rdf:first Nc4c153600000469982f2366e695ccee8
    39 rdf:rest N9f36471dc0a94db985e0daaac7790071
    40 N5af98a3424ec46338ab32d0ff3afb580 schema:name readcube_id
    41 schema:value e24fe362450239badf4370cec55827a43d638bf3dd1cfa39dfb016ff2f937c85
    42 rdf:type schema:PropertyValue
    43 N77e4f5782bfb479992781e7de09cc271 schema:familyName Novák
    44 schema:givenName M.
    45 rdf:type schema:Person
    46 N7d1216572e29442688f787a6b1c418da rdf:first sg:person.015242762255.88
    47 rdf:rest rdf:nil
    48 N9f36471dc0a94db985e0daaac7790071 rdf:first N77e4f5782bfb479992781e7de09cc271
    49 rdf:rest rdf:nil
    50 Nab6bf221150a4a099dcb56825bce1a58 schema:name Praha, Czech Republic
    51 rdf:type schema:Organization
    52 Nb455104c6ae34219aab4abe574b48f35 rdf:first sg:person.015424541177.36
    53 rdf:rest N7d1216572e29442688f787a6b1c418da
    54 Nc01b77e409404b99b746eaf8058c8ea1 schema:name Springer Nature - SN SciGraph project
    55 rdf:type schema:Organization
    56 Nc4c153600000469982f2366e695ccee8 schema:familyName Šidák
    57 schema:givenName Z.
    58 rdf:type schema:Person
    59 Ndc691f09dde545baa52d58dddf017df0 schema:name doi
    60 schema:value 10.1007/978-3-642-51883-6_26
    61 rdf:type schema:PropertyValue
    62 Ne54a2ab912184937aa0c7b0b76a6c09d schema:familyName Havránek
    63 schema:givenName T.
    64 rdf:type schema:Person
    65 Nf3af2cc1312a4bbdbd4ba381b386ae67 schema:name dimensions_id
    66 schema:value pub.1047507966
    67 rdf:type schema:PropertyValue
    68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Information and Computing Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Computation Theory and Mathematics
    73 rdf:type schema:DefinedTerm
    74 sg:person.015242762255.88 schema:affiliation Nab6bf221150a4a099dcb56825bce1a58
    75 schema:familyName Morávek
    76 schema:givenName J.
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015242762255.88
    78 rdf:type schema:Person
    79 sg:person.015424541177.36 schema:familyName Křivánek
    80 schema:givenName M.
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015424541177.36
    82 rdf:type schema:Person
    83 sg:pub.10.1007/bf02289588 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041776510
    84 https://doi.org/10.1007/bf02289588
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1093/biomet/58.1.91 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059418004
    87 rdf:type schema:CreativeWork
     




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


    ...