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 N5584bd5bc563485385109003ef3f4b70
    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 N52a06921498f4226b0ee940f906c1cfb
    23 schema:genre chapter
    24 schema:inLanguage en
    25 schema:isAccessibleForFree true
    26 schema:isPartOf Na45fe16ab0c84cb6a2e46466c02676e5
    27 schema:name New Algorithms for Enumerating All Maximal Cliques
    28 schema:pagination 260-272
    29 schema:productId N23f3ddb3926949579d4c021adf5559c7
    30 N7282b78fcb284c6ea9b341233d81efd9
    31 Nd21b6c3ca2fb4d5b9d96abd184b4e46f
    32 schema:publisher Nb712255130904dca997ba1dcd9c85040
    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 Nbde74b0ac7614ba38ca6310bf9a78918
    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 N11613b86b9964dbe8595560c2240ef3e rdf:first Nde5eda5f3c3a4d9391115631ecbe7aaf
    43 rdf:rest rdf:nil
    44 N2307d6a3afac4510bb1a4fb741659745 rdf:first sg:person.016517167551.57
    45 rdf:rest rdf:nil
    46 N23f3ddb3926949579d4c021adf5559c7 schema:name doi
    47 schema:value 10.1007/978-3-540-27810-8_23
    48 rdf:type schema:PropertyValue
    49 N52a06921498f4226b0ee940f906c1cfb rdf:first Ne87fef4fe0ce4d22ad2363a309b0b6a9
    50 rdf:rest N11613b86b9964dbe8595560c2240ef3e
    51 N5584bd5bc563485385109003ef3f4b70 rdf:first sg:person.07741653331.03
    52 rdf:rest N2307d6a3afac4510bb1a4fb741659745
    53 N7282b78fcb284c6ea9b341233d81efd9 schema:name dimensions_id
    54 schema:value pub.1005823615
    55 rdf:type schema:PropertyValue
    56 Na45fe16ab0c84cb6a2e46466c02676e5 schema:isbn 978-3-540-22339-9
    57 978-3-540-27810-8
    58 schema:name Algorithm Theory - SWAT 2004
    59 rdf:type schema:Book
    60 Nb712255130904dca997ba1dcd9c85040 schema:location Berlin, Heidelberg
    61 schema:name Springer Berlin Heidelberg
    62 rdf:type schema:Organisation
    63 Nbde74b0ac7614ba38ca6310bf9a78918 schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 Nd21b6c3ca2fb4d5b9d96abd184b4e46f schema:name readcube_id
    66 schema:value 1bbe71cf45df3c6b5ec42c4bd47c15b15bfc02e86e3ae7f4d54877d99b0ea08a
    67 rdf:type schema:PropertyValue
    68 Nde5eda5f3c3a4d9391115631ecbe7aaf schema:familyName Katajainen
    69 schema:givenName Jyrki
    70 rdf:type schema:Person
    71 Ne87fef4fe0ce4d22ad2363a309b0b6a9 schema:familyName Hagerup
    72 schema:givenName Torben
    73 rdf:type schema:Person
    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)


    ...