New Algorithms for Enumerating All Maximal Cliques View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Kazuhisa Makino , Takeaki Uno

ABSTRACT

In this paper, we consider the problems of generating all maximal (bipartite) cliques in a given (bipartite) graph G=(V,E) with n vertices and m edges. We propose two algorithms for enumerating all maximal cliques. One runs with O(M(n)) time delay and in O(n2) space and the other runs with O(Δ4) time delay and in O(n+m) space, where Δ denotes the maximum degree of G, M(n) denotes the time needed to multiply two n × n matrices, and the latter one requires O(nm) time as a preprocessing. For a given bipartite graph G, we propose three algorithms for enumerating all maximal bipartite cliques. The first algorithm runs with O(M(n)) time delay and in O(n2) space, which immediately follows from the algorithm for the non-bipartite case. The second one runs with O(Δ3) time delay and in O(n+m) space, and the last one runs with O(Δ2) time delay and in O(n+m+NΔ) space, where N denotes the number of all maximal bipartite cliques in G and both algorithms require O(nm) time as a preprocessing. Our algorithms improve upon all the existing algorithms, when G is either dense or sparse. Furthermore, computational experiments show that our algorithms for sparse graphs have significantly good performance for graphs which are generated randomly and appear in real-world problems. More... »

PAGES

260-272

References to SciGraph publications

  • 2003-11. On Maximal Frequent and Minimal Infrequent Sets in Binary Matrices in ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
  • 1999-01-15. Discovering Frequent Closed Itemsets for Association Rules in DATABASE THEORY — ICDT’99
  • Book

    TITLE

    Algorithm Theory - SWAT 2004

    ISBN

    978-3-540-22339-9
    978-3-540-27810-8

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-27810-8_23

    DOI

    http://dx.doi.org/10.1007/978-3-540-27810-8_23

    DIMENSIONS

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


    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": "Osaka University", 
              "id": "https://www.grid.ac/institutes/grid.136593.b", 
              "name": [
                "Division of Mathematical Science for Social Systems, Graduate School of Engineering Science, Osaka University, 560-8531, Toyonaka, Osaka, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Makino", 
            "givenName": "Kazuhisa", 
            "id": "sg:person.07741653331.03", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07741653331.03"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "National Institute of Informatics", 
              "id": "https://www.grid.ac/institutes/grid.250343.3", 
              "name": [
                "National Institute or Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, 101-8430, Tokyo, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Uno", 
            "givenName": "Takeaki", 
            "id": "sg:person.016517167551.57", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016517167551.57"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/s1389-1286(99)00040-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000088953"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(95)00026-n", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013152121"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(94)90121-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019594521"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(88)90065-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022531339"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(94)00069-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030594454"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0747-7171(08)80013-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033876399"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1024605820527", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043856204", 
              "https://doi.org/10.1023/a:1024605820527"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49257-7_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048579740", 
              "https://doi.org/10.1007/3-540-49257-7_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49257-7_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048579740", 
              "https://doi.org/10.1007/3-540-49257-7_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0206036", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841375"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0209042", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841531"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0214017", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841806"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539701388768", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879304"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s009753970240639x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879376"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.1975.5.3.237", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1092631557"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511569913", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098666427"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "In this paper, we consider the problems of generating all maximal (bipartite) cliques in a given (bipartite) graph G=(V,E) with n vertices and m edges. We propose two algorithms for enumerating all maximal cliques. One runs with O(M(n)) time delay and in O(n2) space and the other runs with O(\u03944) time delay and in O(n+m) space, where \u0394 denotes the maximum degree of G, M(n) denotes the time needed to multiply two n \u00d7 n matrices, and the latter one requires O(nm) time as a preprocessing. For a given bipartite graph G, we propose three algorithms for enumerating all maximal bipartite cliques. The first algorithm runs with O(M(n)) time delay and in O(n2) space, which immediately follows from the algorithm for the non-bipartite case. The second one runs with O(\u03943) time delay and in O(n+m) space, and the last one runs with O(\u03942) time delay and in O(n+m+N\u0394) space, where N denotes the number of all maximal bipartite cliques in G and both algorithms require O(nm) time as a preprocessing. Our algorithms improve upon all the existing algorithms, when G is either dense or sparse. Furthermore, computational experiments show that our algorithms for sparse graphs have significantly good performance for graphs which are generated randomly and appear in real-world problems.", 
        "editor": [
          {
            "familyName": "Hagerup", 
            "givenName": "Torben", 
            "type": "Person"
          }, 
          {
            "familyName": "Katajainen", 
            "givenName": "Jyrki", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-27810-8_23", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-22339-9", 
            "978-3-540-27810-8"
          ], 
          "name": "Algorithm Theory - SWAT 2004", 
          "type": "Book"
        }, 
        "name": "New Algorithms for Enumerating All Maximal Cliques", 
        "pagination": "260-272", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1005823615"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-27810-8_23"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "1bbe71cf45df3c6b5ec42c4bd47c15b15bfc02e86e3ae7f4d54877d99b0ea08a"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-27810-8_23", 
          "https://app.dimensions.ai/details/publication/pub.1005823615"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:22", 
        "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/0000000363_0000000363/records_70032_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-27810-8_23"
      }
    ]
     

    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-540-27810-8_23'

    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-540-27810-8_23'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27810-8_23'

    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-540-27810-8_23'


     

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

    127 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-27810-8_23 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N982b61299c2c4daaa02880c30a0d55a3
    4 schema:citation sg:pub.10.1007/3-540-49257-7_25
    5 sg:pub.10.1023/a:1024605820527
    6 https://doi.org/10.1002/net.1975.5.3.237
    7 https://doi.org/10.1016/0004-3702(94)00069-7
    8 https://doi.org/10.1016/0020-0190(88)90065-8
    9 https://doi.org/10.1016/0020-0190(94)90121-x
    10 https://doi.org/10.1016/0166-218x(95)00026-n
    11 https://doi.org/10.1016/s0747-7171(08)80013-2
    12 https://doi.org/10.1016/s1389-1286(99)00040-7
    13 https://doi.org/10.1017/cbo9780511569913
    14 https://doi.org/10.1137/0206036
    15 https://doi.org/10.1137/0209042
    16 https://doi.org/10.1137/0214017
    17 https://doi.org/10.1137/s0097539701388768
    18 https://doi.org/10.1137/s009753970240639x
    19 schema:datePublished 2004
    20 schema:datePublishedReg 2004-01-01
    21 schema:description In this paper, we consider the problems of generating all maximal (bipartite) cliques in a given (bipartite) graph G=(V,E) with n vertices and m edges. We propose two algorithms for enumerating all maximal cliques. One runs with O(M(n)) time delay and in O(n2) space and the other runs with O(Δ4) time delay and in O(n+m) space, where Δ denotes the maximum degree of G, M(n) denotes the time needed to multiply two n × n matrices, and the latter one requires O(nm) time as a preprocessing. For a given bipartite graph G, we propose three algorithms for enumerating all maximal bipartite cliques. The first algorithm runs with O(M(n)) time delay and in O(n2) space, which immediately follows from the algorithm for the non-bipartite case. The second one runs with O(Δ3) time delay and in O(n+m) space, and the last one runs with O(Δ2) time delay and in O(n+m+NΔ) space, where N denotes the number of all maximal bipartite cliques in G and both algorithms require O(nm) time as a preprocessing. Our algorithms improve upon all the existing algorithms, when G is either dense or sparse. Furthermore, computational experiments show that our algorithms for sparse graphs have significantly good performance for graphs which are generated randomly and appear in real-world problems.
    22 schema:editor N5174679d7ccc40fa85ab7edc98b51e65
    23 schema:genre chapter
    24 schema:inLanguage en
    25 schema:isAccessibleForFree true
    26 schema:isPartOf Nc429c7bb07664a8480d6b29dc6003a11
    27 schema:name New Algorithms for Enumerating All Maximal Cliques
    28 schema:pagination 260-272
    29 schema:productId N2781fb99e8b247dd886e14397aae840d
    30 N6e45e1bea0e743e6a0793b4959c36755
    31 N95916246fda64e769c2c52023caf2669
    32 schema:publisher N46a4cd56c8284c0da455b1f3c721ca0e
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005823615
    34 https://doi.org/10.1007/978-3-540-27810-8_23
    35 schema:sdDatePublished 2019-04-16T08:22
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher Nc5ae7d5bf0a24b5fb8505b2500c2ec6c
    38 schema:url https://link.springer.com/10.1007%2F978-3-540-27810-8_23
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset chapters
    41 rdf:type schema:Chapter
    42 N04786c71340e4190b6cee47e6647c8ee rdf:first N32619a9e635945bb842ac210988de91e
    43 rdf:rest rdf:nil
    44 N1a63e541c2c646cabe4158d058a88549 schema:familyName Hagerup
    45 schema:givenName Torben
    46 rdf:type schema:Person
    47 N2781fb99e8b247dd886e14397aae840d schema:name doi
    48 schema:value 10.1007/978-3-540-27810-8_23
    49 rdf:type schema:PropertyValue
    50 N32619a9e635945bb842ac210988de91e schema:familyName Katajainen
    51 schema:givenName Jyrki
    52 rdf:type schema:Person
    53 N46a4cd56c8284c0da455b1f3c721ca0e schema:location Berlin, Heidelberg
    54 schema:name Springer Berlin Heidelberg
    55 rdf:type schema:Organisation
    56 N5174679d7ccc40fa85ab7edc98b51e65 rdf:first N1a63e541c2c646cabe4158d058a88549
    57 rdf:rest N04786c71340e4190b6cee47e6647c8ee
    58 N6e45e1bea0e743e6a0793b4959c36755 schema:name readcube_id
    59 schema:value 1bbe71cf45df3c6b5ec42c4bd47c15b15bfc02e86e3ae7f4d54877d99b0ea08a
    60 rdf:type schema:PropertyValue
    61 N914a794633844c86b239f25fbec1a240 rdf:first sg:person.016517167551.57
    62 rdf:rest rdf:nil
    63 N95916246fda64e769c2c52023caf2669 schema:name dimensions_id
    64 schema:value pub.1005823615
    65 rdf:type schema:PropertyValue
    66 N982b61299c2c4daaa02880c30a0d55a3 rdf:first sg:person.07741653331.03
    67 rdf:rest N914a794633844c86b239f25fbec1a240
    68 Nc429c7bb07664a8480d6b29dc6003a11 schema:isbn 978-3-540-22339-9
    69 978-3-540-27810-8
    70 schema:name Algorithm Theory - SWAT 2004
    71 rdf:type schema:Book
    72 Nc5ae7d5bf0a24b5fb8505b2500c2ec6c schema:name Springer Nature - SN SciGraph project
    73 rdf:type schema:Organization
    74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Information and Computing Sciences
    76 rdf:type schema:DefinedTerm
    77 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Computation Theory and Mathematics
    79 rdf:type schema:DefinedTerm
    80 sg:person.016517167551.57 schema:affiliation https://www.grid.ac/institutes/grid.250343.3
    81 schema:familyName Uno
    82 schema:givenName Takeaki
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016517167551.57
    84 rdf:type schema:Person
    85 sg:person.07741653331.03 schema:affiliation https://www.grid.ac/institutes/grid.136593.b
    86 schema:familyName Makino
    87 schema:givenName Kazuhisa
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07741653331.03
    89 rdf:type schema:Person
    90 sg:pub.10.1007/3-540-49257-7_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048579740
    91 https://doi.org/10.1007/3-540-49257-7_25
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1023/a:1024605820527 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043856204
    94 https://doi.org/10.1023/a:1024605820527
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1002/net.1975.5.3.237 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092631557
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/0004-3702(94)00069-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030594454
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/0020-0190(88)90065-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022531339
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/0020-0190(94)90121-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1019594521
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/0166-218x(95)00026-n schema:sameAs https://app.dimensions.ai/details/publication/pub.1013152121
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/s0747-7171(08)80013-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033876399
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1016/s1389-1286(99)00040-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000088953
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1017/cbo9780511569913 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098666427
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1137/0206036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841375
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1137/0209042 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841531
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1137/0214017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841806
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1137/s0097539701388768 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879304
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1137/s009753970240639x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879376
    121 rdf:type schema:CreativeWork
    122 https://www.grid.ac/institutes/grid.136593.b schema:alternateName Osaka University
    123 schema:name Division of Mathematical Science for Social Systems, Graduate School of Engineering Science, Osaka University, 560-8531, Toyonaka, Osaka, Japan
    124 rdf:type schema:Organization
    125 https://www.grid.ac/institutes/grid.250343.3 schema:alternateName National Institute of Informatics
    126 schema:name National Institute or Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, 101-8430, Tokyo, Japan
    127 rdf:type schema:Organization
     




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


    ...