Approximability of the Minimum Bisection Problem: An Algorithmic Challenge View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-10-04

AUTHORS

Marek Karpinski

ABSTRACT

We survey some recent results on the complexity of computing approximate solutions for instances of the Minimum Bisection problem and formulate some very intriguing and still open questions about the approximability status of that problem.

PAGES

59-67

Book

TITLE

Mathematical Foundations of Computer Science 2002

ISBN

978-3-540-44040-6
978-3-540-45687-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45687-2_4

DOI

http://dx.doi.org/10.1007/3-540-45687-2_4

DIMENSIONS

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


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": "University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "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"
      }
    ], 
    "datePublished": "2002-10-04", 
    "datePublishedReg": "2002-10-04", 
    "description": "We survey some recent results on the complexity of computing approximate solutions for instances of the Minimum Bisection problem and formulate some very intriguing and still open questions about the approximability status of that problem.", 
    "editor": [
      {
        "familyName": "Diks", 
        "givenName": "Krzysztof", 
        "type": "Person"
      }, 
      {
        "familyName": "Rytter", 
        "givenName": "Wojciech", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45687-2_4", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-44040-6", 
        "978-3-540-45687-2"
      ], 
      "name": "Mathematical Foundations of Computer Science 2002", 
      "type": "Book"
    }, 
    "keywords": [
      "bisection problem", 
      "minimum bisection problem", 
      "algorithmic challenges", 
      "approximability status", 
      "complexity", 
      "approximability", 
      "open question", 
      "approximate solution", 
      "instances", 
      "challenges", 
      "solution", 
      "recent results", 
      "results", 
      "questions", 
      "status", 
      "problem"
    ], 
    "name": "Approximability of the Minimum Bisection Problem: An Algorithmic Challenge", 
    "pagination": "59-67", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026123410"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45687-2_4"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45687-2_4", 
      "https://app.dimensions.ai/details/publication/pub.1026123410"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:52", 
    "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_37.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45687-2_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-45687-2_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-45687-2_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45687-2_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-45687-2_4'


 

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

80 TRIPLES      22 PREDICATES      40 URIs      33 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45687-2_4 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N3fbb8fa1c1f94492b8d7d015df60ea39
4 schema:datePublished 2002-10-04
5 schema:datePublishedReg 2002-10-04
6 schema:description We survey some recent results on the complexity of computing approximate solutions for instances of the Minimum Bisection problem and formulate some very intriguing and still open questions about the approximability status of that problem.
7 schema:editor Na76a7ec267764fa293dfa7197043c647
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N35006f400df141a1ad897677f3aadacd
11 schema:keywords algorithmic challenges
12 approximability
13 approximability status
14 approximate solution
15 bisection problem
16 challenges
17 complexity
18 instances
19 minimum bisection problem
20 open question
21 problem
22 questions
23 recent results
24 results
25 solution
26 status
27 schema:name Approximability of the Minimum Bisection Problem: An Algorithmic Challenge
28 schema:pagination 59-67
29 schema:productId Na1fb17625d284e6fa3da9b2b8e558606
30 Ne438a250321041e89d347d77efbfff77
31 schema:publisher N5b9cd16f05de41e29422ea069f7a9b39
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026123410
33 https://doi.org/10.1007/3-540-45687-2_4
34 schema:sdDatePublished 2022-12-01T06:52
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher Nf23db657eeb248f189491707accd0950
37 schema:url https://doi.org/10.1007/3-540-45687-2_4
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N288993f1f1da4558b14b6f00fc9a3f70 schema:familyName Rytter
42 schema:givenName Wojciech
43 rdf:type schema:Person
44 N2cac365999754e6f8a8d41ce8d070c44 rdf:first N288993f1f1da4558b14b6f00fc9a3f70
45 rdf:rest rdf:nil
46 N35006f400df141a1ad897677f3aadacd schema:isbn 978-3-540-44040-6
47 978-3-540-45687-2
48 schema:name Mathematical Foundations of Computer Science 2002
49 rdf:type schema:Book
50 N3fbb8fa1c1f94492b8d7d015df60ea39 rdf:first sg:person.011636042271.02
51 rdf:rest rdf:nil
52 N5b9cd16f05de41e29422ea069f7a9b39 schema:name Springer Nature
53 rdf:type schema:Organisation
54 N6a5577baefa5443ba5a1491a45ae7fd3 schema:familyName Diks
55 schema:givenName Krzysztof
56 rdf:type schema:Person
57 Na1fb17625d284e6fa3da9b2b8e558606 schema:name dimensions_id
58 schema:value pub.1026123410
59 rdf:type schema:PropertyValue
60 Na76a7ec267764fa293dfa7197043c647 rdf:first N6a5577baefa5443ba5a1491a45ae7fd3
61 rdf:rest N2cac365999754e6f8a8d41ce8d070c44
62 Ne438a250321041e89d347d77efbfff77 schema:name doi
63 schema:value 10.1007/3-540-45687-2_4
64 rdf:type schema:PropertyValue
65 Nf23db657eeb248f189491707accd0950 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
68 schema:name Information and Computing Sciences
69 rdf:type schema:DefinedTerm
70 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
71 schema:name Computation Theory and Mathematics
72 rdf:type schema:DefinedTerm
73 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
74 schema:familyName Karpinski
75 schema:givenName Marek
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
77 rdf:type schema:Person
78 grid-institutes:grid.10388.32 schema:alternateName University of Bonn, Germany
79 schema:name University of Bonn, Germany
80 rdf:type schema:Organization
 




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


...