Approximate Counting of Matchings in (3,3)-Hypergraphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Andrzej Dudek , Marek Karpinski , Andrzej Ruciński , Edyta Szymańska

ABSTRACT

We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as (3,3)-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting problem for 3-partite (3,3)-hypergraphs. The proof technique of this paper uses the general correlation decay technique and a new combinatorial analysis of the underlying structures of the intersection graphs. The proof method could be also of independent interest. More... »

PAGES

380-391

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-08404-6_33

DOI

http://dx.doi.org/10.1007/978-3-319-08404-6_33

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Western Michigan University, Kalamazoo, MI, USA", 
          "id": "http://www.grid.ac/institutes/grid.268187.2", 
          "name": [
            "Western Michigan University, Kalamazoo, MI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dudek", 
        "givenName": "Andrzej", 
        "id": "sg:person.012773057751.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012773057751.96"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Department of Computer Science, University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Pozna\u0144, Poland", 
          "id": "http://www.grid.ac/institutes/grid.5633.3", 
          "name": [
            "Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Pozna\u0144, Poland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ruci\u0144ski", 
        "givenName": "Andrzej", 
        "id": "sg:person.015322164316.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015322164316.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Pozna\u0144, Poland", 
          "id": "http://www.grid.ac/institutes/grid.5633.3", 
          "name": [
            "Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Pozna\u0144, Poland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Szyma\u0144ska", 
        "givenName": "Edyta", 
        "id": "sg:person.014260054065.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014260054065.30"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as (3,3)-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting problem for 3-partite (3,3)-hypergraphs. The proof technique of this paper uses the general correlation decay technique and a new combinatorial analysis of the underlying structures of the intersection graphs. The proof method could be also of independent interest.", 
    "editor": [
      {
        "familyName": "Ravi", 
        "givenName": "R.", 
        "type": "Person"
      }, 
      {
        "familyName": "G\u00f8rtz", 
        "givenName": "Inge Li", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-08404-6_33", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-08403-9", 
        "978-3-319-08404-6"
      ], 
      "name": "Algorithm Theory \u2013 SWAT 2014", 
      "type": "Book"
    }, 
    "keywords": [
      "polynomial time approximation scheme", 
      "time approximation scheme", 
      "approximation scheme", 
      "first polynomial-time approximation scheme", 
      "number of matchings", 
      "maximum degree three", 
      "new combinatorial analysis", 
      "approximate counting", 
      "intersection graph", 
      "counting problem", 
      "independent interest", 
      "degree three", 
      "special case", 
      "combinatorial analysis", 
      "proof technique", 
      "hypergraphs", 
      "proof method", 
      "scheme", 
      "problem", 
      "decay technique", 
      "graph", 
      "matching", 
      "technique", 
      "number", 
      "structure", 
      "cases", 
      "three", 
      "interest", 
      "analysis", 
      "counting", 
      "method", 
      "paper"
    ], 
    "name": "Approximate Counting of Matchings in (3,3)-Hypergraphs", 
    "pagination": "380-391", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004668718"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-08404-6_33"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-08404-6_33", 
      "https://app.dimensions.ai/details/publication/pub.1004668718"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_462.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-08404-6_33"
  }
]
 

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-319-08404-6_33'

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-319-08404-6_33'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-08404-6_33'

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-319-08404-6_33'


 

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

123 TRIPLES      22 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-08404-6_33 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N41bf0c46e1fb4661a6bc36fee7be9918
4 schema:datePublished 2014
5 schema:datePublishedReg 2014-01-01
6 schema:description We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as (3,3)-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting problem for 3-partite (3,3)-hypergraphs. The proof technique of this paper uses the general correlation decay technique and a new combinatorial analysis of the underlying structures of the intersection graphs. The proof method could be also of independent interest.
7 schema:editor N21cdd84ee9d046e7b666e5101de7400f
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Na2e268b24a9b46328b2524a4595bb202
11 schema:keywords analysis
12 approximate counting
13 approximation scheme
14 cases
15 combinatorial analysis
16 counting
17 counting problem
18 decay technique
19 degree three
20 first polynomial-time approximation scheme
21 graph
22 hypergraphs
23 independent interest
24 interest
25 intersection graph
26 matching
27 maximum degree three
28 method
29 new combinatorial analysis
30 number
31 number of matchings
32 paper
33 polynomial time approximation scheme
34 problem
35 proof method
36 proof technique
37 scheme
38 special case
39 structure
40 technique
41 three
42 time approximation scheme
43 schema:name Approximate Counting of Matchings in (3,3)-Hypergraphs
44 schema:pagination 380-391
45 schema:productId N71387c204521459daf7301aedb8346c7
46 Nf69bda6eceff4fe1bf993c72fb90984c
47 schema:publisher N7ed230e75ae246b281257ef52409526e
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004668718
49 https://doi.org/10.1007/978-3-319-08404-6_33
50 schema:sdDatePublished 2022-12-01T06:54
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher Ne1629fe98e314afbbb0a195937fc477e
53 schema:url https://doi.org/10.1007/978-3-319-08404-6_33
54 sgo:license sg:explorer/license/
55 sgo:sdDataset chapters
56 rdf:type schema:Chapter
57 N21cdd84ee9d046e7b666e5101de7400f rdf:first N9800f8458a4e481c861ca62dbf752ce7
58 rdf:rest Nca1a7a623075479c9fc746dc01d99b2b
59 N41bf0c46e1fb4661a6bc36fee7be9918 rdf:first sg:person.012773057751.96
60 rdf:rest N4a9192635fbd4e08accf1fb297d3ffdc
61 N4a9192635fbd4e08accf1fb297d3ffdc rdf:first sg:person.011636042271.02
62 rdf:rest N4f2a24a05446420f9e38ec833f9ac6d6
63 N4baec39f08544b8fa1d89ee35e451e84 schema:familyName Gørtz
64 schema:givenName Inge Li
65 rdf:type schema:Person
66 N4f2a24a05446420f9e38ec833f9ac6d6 rdf:first sg:person.015322164316.14
67 rdf:rest Ne16bb3ca4aad4e50a42879fbb219a335
68 N71387c204521459daf7301aedb8346c7 schema:name doi
69 schema:value 10.1007/978-3-319-08404-6_33
70 rdf:type schema:PropertyValue
71 N7ed230e75ae246b281257ef52409526e schema:name Springer Nature
72 rdf:type schema:Organisation
73 N9800f8458a4e481c861ca62dbf752ce7 schema:familyName Ravi
74 schema:givenName R.
75 rdf:type schema:Person
76 Na2e268b24a9b46328b2524a4595bb202 schema:isbn 978-3-319-08403-9
77 978-3-319-08404-6
78 schema:name Algorithm Theory – SWAT 2014
79 rdf:type schema:Book
80 Nca1a7a623075479c9fc746dc01d99b2b rdf:first N4baec39f08544b8fa1d89ee35e451e84
81 rdf:rest rdf:nil
82 Ne1629fe98e314afbbb0a195937fc477e schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 Ne16bb3ca4aad4e50a42879fbb219a335 rdf:first sg:person.014260054065.30
85 rdf:rest rdf:nil
86 Nf69bda6eceff4fe1bf993c72fb90984c schema:name dimensions_id
87 schema:value pub.1004668718
88 rdf:type schema:PropertyValue
89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
90 schema:name Information and Computing Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
93 schema:name Computation Theory and Mathematics
94 rdf:type schema:DefinedTerm
95 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
96 schema:familyName Karpinski
97 schema:givenName Marek
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
99 rdf:type schema:Person
100 sg:person.012773057751.96 schema:affiliation grid-institutes:grid.268187.2
101 schema:familyName Dudek
102 schema:givenName Andrzej
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012773057751.96
104 rdf:type schema:Person
105 sg:person.014260054065.30 schema:affiliation grid-institutes:grid.5633.3
106 schema:familyName Szymańska
107 schema:givenName Edyta
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014260054065.30
109 rdf:type schema:Person
110 sg:person.015322164316.14 schema:affiliation grid-institutes:grid.5633.3
111 schema:familyName Ruciński
112 schema:givenName Andrzej
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015322164316.14
114 rdf:type schema:Person
115 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn, Germany
116 schema:name Department of Computer Science, University of Bonn, Germany
117 rdf:type schema:Organization
118 grid-institutes:grid.268187.2 schema:alternateName Western Michigan University, Kalamazoo, MI, USA
119 schema:name Western Michigan University, Kalamazoo, MI, USA
120 rdf:type schema:Organization
121 grid-institutes:grid.5633.3 schema:alternateName Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland
122 schema:name Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland
123 rdf:type schema:Organization
 




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


...