A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999-11-19

AUTHORS

T. Calamoneri , I. Finocchi , R. Petreschi , Y. Manoussakis

ABSTRACT

We deal with the maximum cut problem on cubic graphs and we present a simple O(log n) time parallel algorithm, running on a CRCW PRAM with O(n) processors. The approximation ratio of our algorithm is and improves the best known parallel approximation ratio, i.e. 2, in the special case of cubic graphs. More... »

PAGES

27-36

References to SciGraph publications

Book

TITLE

Advances in Computing Science — ASIAN’99

ISBN

978-3-540-66856-5
978-3-540-46674-1

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-46674-6_4

DOI

http://dx.doi.org/10.1007/3-540-46674-6_4

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "Dept. of Computer Science - Univ. of Rome, La Sapienza, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Calamoneri", 
        "givenName": "T.", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Dept. of Computer Science - Univ. of Rome, La Sapienza, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Finocchi", 
        "givenName": "I.", 
        "id": "sg:person.014240412541.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Dept. of Computer Science - Univ. of Rome, La Sapienza, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Petreschi", 
        "givenName": "R.", 
        "id": "sg:person.011402427702.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Paris-Sud", 
          "id": "https://www.grid.ac/institutes/grid.5842.b", 
          "name": [
            "Dept. of Computer Science - Univ. Paris Sud, Orsay, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Manoussakis", 
        "givenName": "Y.", 
        "id": "sg:person.012004232654.36", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012004232654.36"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02523688", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007563368", 
          "https://doi.org/10.1007/bf02523688"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02523688", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007563368", 
          "https://doi.org/10.1007/bf02523688"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-63774-5_98", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018375055", 
          "https://doi.org/10.1007/3-540-63774-5_98"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(86)80023-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020514024"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/eujc.1993.1035", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038087222"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(91)90023-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043200457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/800133.804355", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044392747"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/234782.234783", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048822402"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(76)90059-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052030997"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0215074", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841936"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539793245350", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879810"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1999-11-19", 
    "datePublishedReg": "1999-11-19", 
    "description": "We deal with the maximum cut problem on cubic graphs and we present a simple O(log n) time parallel algorithm, running on a CRCW PRAM with O(n) processors. The approximation ratio of our algorithm is and improves the best known parallel approximation ratio, i.e. 2, in the special case of cubic graphs.", 
    "editor": [
      {
        "familyName": "Thiagarajan", 
        "givenName": "P. S.", 
        "type": "Person"
      }, 
      {
        "familyName": "Yap", 
        "givenName": "Roland", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-46674-6_4", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66856-5", 
        "978-3-540-46674-1"
      ], 
      "name": "Advances in Computing Science \u2014 ASIAN\u201999", 
      "type": "Book"
    }, 
    "name": "A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs", 
    "pagination": "27-36", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-46674-6_4"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ca0b60df187f6d6758a1290bcbd0cc437e4b508be1c44c0ca94bff0dc84e7bec"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1042415512"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-46674-6_4", 
      "https://app.dimensions.ai/details/publication/pub.1042415512"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:48", 
    "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/0000000347_0000000347/records_89819_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-46674-6_4"
  }
]
 

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/3-540-46674-6_4'

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/3-540-46674-6_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-46674-6_4'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-46674-6_4'


 

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

128 TRIPLES      23 PREDICATES      36 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-46674-6_4 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N9d8269ecc61848dc8f053f7ffec5df78
4 schema:citation sg:pub.10.1007/3-540-63774-5_98
5 sg:pub.10.1007/bf02523688
6 https://doi.org/10.1006/eujc.1993.1035
7 https://doi.org/10.1016/0022-0000(91)90023-x
8 https://doi.org/10.1016/0304-3975(76)90059-1
9 https://doi.org/10.1016/s0019-9958(86)80023-7
10 https://doi.org/10.1137/0215074
11 https://doi.org/10.1137/s0097539793245350
12 https://doi.org/10.1145/234782.234783
13 https://doi.org/10.1145/800133.804355
14 schema:datePublished 1999-11-19
15 schema:datePublishedReg 1999-11-19
16 schema:description We deal with the maximum cut problem on cubic graphs and we present a simple O(log n) time parallel algorithm, running on a CRCW PRAM with O(n) processors. The approximation ratio of our algorithm is and improves the best known parallel approximation ratio, i.e. 2, in the special case of cubic graphs.
17 schema:editor N80bc84d1c699459a9f3f59215ee627dc
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf N9f396cbc19784d6691559f6c0928a5ce
22 schema:name A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs
23 schema:pagination 27-36
24 schema:productId N3a6a36a8eacd44be916bd07e34f0f674
25 N6a92d4cd915d42eebc3f498996363969
26 N9e54ce1385844a57a36681d538b49f2d
27 schema:publisher Ncc815153c73c4967b7f8c159ee3dfc99
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042415512
29 https://doi.org/10.1007/3-540-46674-6_4
30 schema:sdDatePublished 2019-04-16T05:48
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher Nfb849d245077453aa355dedef22f735b
33 schema:url https://link.springer.com/10.1007%2F3-540-46674-6_4
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N3a6a36a8eacd44be916bd07e34f0f674 schema:name dimensions_id
38 schema:value pub.1042415512
39 rdf:type schema:PropertyValue
40 N4d123052a87f4344a648666a3926b25c schema:familyName Thiagarajan
41 schema:givenName P. S.
42 rdf:type schema:Person
43 N59c4179407d345708e278ea2e593ed3b rdf:first sg:person.014240412541.72
44 rdf:rest Nd13ed51ab9614069a7e19661703f3ccd
45 N6a92d4cd915d42eebc3f498996363969 schema:name doi
46 schema:value 10.1007/3-540-46674-6_4
47 rdf:type schema:PropertyValue
48 N745e9d724a4a4d99a452b969d0e9915d schema:name Dept. of Computer Science - Univ. of Rome, La Sapienza, Italy
49 rdf:type schema:Organization
50 N791a5644ec884721b5c0723cb6299b3e rdf:first Nc0974ab257e34d428f08df56d3320ab3
51 rdf:rest rdf:nil
52 N80bc84d1c699459a9f3f59215ee627dc rdf:first N4d123052a87f4344a648666a3926b25c
53 rdf:rest N791a5644ec884721b5c0723cb6299b3e
54 N95db9c2902c348c9a8ed04abc31ea3b3 schema:name Dept. of Computer Science - Univ. of Rome, La Sapienza, Italy
55 rdf:type schema:Organization
56 N9d8269ecc61848dc8f053f7ffec5df78 rdf:first Nb50cffb1c441406d922cddae8b9b0235
57 rdf:rest N59c4179407d345708e278ea2e593ed3b
58 N9e54ce1385844a57a36681d538b49f2d schema:name readcube_id
59 schema:value ca0b60df187f6d6758a1290bcbd0cc437e4b508be1c44c0ca94bff0dc84e7bec
60 rdf:type schema:PropertyValue
61 N9f396cbc19784d6691559f6c0928a5ce schema:isbn 978-3-540-46674-1
62 978-3-540-66856-5
63 schema:name Advances in Computing Science — ASIAN’99
64 rdf:type schema:Book
65 Nb50cffb1c441406d922cddae8b9b0235 schema:affiliation Nedee0bb43ea248c39fba9ab400a2d1e9
66 schema:familyName Calamoneri
67 schema:givenName T.
68 rdf:type schema:Person
69 Nc0974ab257e34d428f08df56d3320ab3 schema:familyName Yap
70 schema:givenName Roland
71 rdf:type schema:Person
72 Ncc815153c73c4967b7f8c159ee3dfc99 schema:location Berlin, Heidelberg
73 schema:name Springer Berlin Heidelberg
74 rdf:type schema:Organisation
75 Nd13ed51ab9614069a7e19661703f3ccd rdf:first sg:person.011402427702.78
76 rdf:rest Nfe38ac7f6b744a718ac0ab1c78b20fdd
77 Nedee0bb43ea248c39fba9ab400a2d1e9 schema:name Dept. of Computer Science - Univ. of Rome, La Sapienza, Italy
78 rdf:type schema:Organization
79 Nfb849d245077453aa355dedef22f735b schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 Nfe38ac7f6b744a718ac0ab1c78b20fdd rdf:first sg:person.012004232654.36
82 rdf:rest rdf:nil
83 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
84 schema:name Mathematical Sciences
85 rdf:type schema:DefinedTerm
86 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
87 schema:name Numerical and Computational Mathematics
88 rdf:type schema:DefinedTerm
89 sg:person.011402427702.78 schema:affiliation N95db9c2902c348c9a8ed04abc31ea3b3
90 schema:familyName Petreschi
91 schema:givenName R.
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
93 rdf:type schema:Person
94 sg:person.012004232654.36 schema:affiliation https://www.grid.ac/institutes/grid.5842.b
95 schema:familyName Manoussakis
96 schema:givenName Y.
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012004232654.36
98 rdf:type schema:Person
99 sg:person.014240412541.72 schema:affiliation N745e9d724a4a4d99a452b969d0e9915d
100 schema:familyName Finocchi
101 schema:givenName I.
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72
103 rdf:type schema:Person
104 sg:pub.10.1007/3-540-63774-5_98 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018375055
105 https://doi.org/10.1007/3-540-63774-5_98
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/bf02523688 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007563368
108 https://doi.org/10.1007/bf02523688
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1006/eujc.1993.1035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038087222
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/0022-0000(91)90023-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043200457
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/0304-3975(76)90059-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052030997
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/s0019-9958(86)80023-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020514024
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1137/0215074 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841936
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1137/s0097539793245350 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879810
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/234782.234783 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048822402
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/800133.804355 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044392747
125 rdf:type schema:CreativeWork
126 https://www.grid.ac/institutes/grid.5842.b schema:alternateName University of Paris-Sud
127 schema:name Dept. of Computer Science - Univ. Paris Sud, Orsay, France
128 rdf:type schema:Organization
 




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


...