Approximating Maximum Edge 2-Coloring in Simple Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Zhi-Zhong Chen , Sayuri Konno , Yuki Matsushita

ABSTRACT

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in O(n3m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial-time approximation algorithm was \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{5}{6}\approx 0.833$\end{document}. More... »

PAGES

78-89

Book

TITLE

Algorithmic Aspects in Information and Management

ISBN

978-3-642-14354-0
978-3-642-14355-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14355-7_9

DOI

http://dx.doi.org/10.1007/978-3-642-14355-7_9

DIMENSIONS

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


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": "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Konno", 
        "givenName": "Sayuri", 
        "id": "sg:person.015122631215.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015122631215.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Matsushita", 
        "givenName": "Yuki", 
        "id": "sg:person.015720211615.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015720211615.58"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in O(n3m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial-time approximation algorithm was \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\frac{5}{6}\\approx 0.833$\\end{document}.", 
    "editor": [
      {
        "familyName": "Chen", 
        "givenName": "Bo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-14355-7_9", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-14354-0", 
        "978-3-642-14355-7"
      ], 
      "name": "Algorithmic Aspects in Information and Management", 
      "type": "Book"
    }, 
    "keywords": [
      "polynomial-time approximation algorithm", 
      "simple graph", 
      "approximation algorithm", 
      "number of vertices", 
      "input graph", 
      "approximation ratio", 
      "maximum edge", 
      "graph", 
      "algorithm", 
      "vertices", 
      "edge", 
      "best ratio", 
      "number", 
      "ratio", 
      "run", 
      "time", 
      "color"
    ], 
    "name": "Approximating Maximum Edge 2-Coloring in Simple Graphs", 
    "pagination": "78-89", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011594790"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-14355-7_9"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-14355-7_9", 
      "https://app.dimensions.ai/details/publication/pub.1011594790"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_291.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-14355-7_9"
  }
]
 

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-642-14355-7_9'

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-642-14355-7_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14355-7_9'

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-642-14355-7_9'


 

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

91 TRIPLES      23 PREDICATES      43 URIs      36 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-14355-7_9 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N1292c66086bd45b59dbdbeefcc951cfb
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in O(n3m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial-time approximation algorithm was \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{5}{6}\approx 0.833$\end{document}.
7 schema:editor Nc3c31917cc6342c58ad15e4573e339cb
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nfe6ae460674f4b119335ae8cd659b805
12 schema:keywords algorithm
13 approximation algorithm
14 approximation ratio
15 best ratio
16 color
17 edge
18 graph
19 input graph
20 maximum edge
21 number
22 number of vertices
23 polynomial-time approximation algorithm
24 ratio
25 run
26 simple graph
27 time
28 vertices
29 schema:name Approximating Maximum Edge 2-Coloring in Simple Graphs
30 schema:pagination 78-89
31 schema:productId N01da1fb695d444b9a02868fda3242a23
32 Ne683fe9dada54b73aa4e3dc07f23c34e
33 schema:publisher N9e9378c471a943c98e592fa93946553c
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011594790
35 https://doi.org/10.1007/978-3-642-14355-7_9
36 schema:sdDatePublished 2022-05-20T07:45
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher N62be50a5a2b847a1bb55356db9979585
39 schema:url https://doi.org/10.1007/978-3-642-14355-7_9
40 sgo:license sg:explorer/license/
41 sgo:sdDataset chapters
42 rdf:type schema:Chapter
43 N01da1fb695d444b9a02868fda3242a23 schema:name doi
44 schema:value 10.1007/978-3-642-14355-7_9
45 rdf:type schema:PropertyValue
46 N02c5c028d3734b7f9d9c9563d1c0ebb6 rdf:first sg:person.015122631215.98
47 rdf:rest N61bb8803f8b44375b9ec5b0dc6d996ac
48 N1292c66086bd45b59dbdbeefcc951cfb rdf:first sg:person.015654265661.98
49 rdf:rest N02c5c028d3734b7f9d9c9563d1c0ebb6
50 N452dbc7df9c6435ea8c846d9263b6385 schema:familyName Chen
51 schema:givenName Bo
52 rdf:type schema:Person
53 N61bb8803f8b44375b9ec5b0dc6d996ac rdf:first sg:person.015720211615.58
54 rdf:rest rdf:nil
55 N62be50a5a2b847a1bb55356db9979585 schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 N9e9378c471a943c98e592fa93946553c schema:name Springer Nature
58 rdf:type schema:Organisation
59 Nc3c31917cc6342c58ad15e4573e339cb rdf:first N452dbc7df9c6435ea8c846d9263b6385
60 rdf:rest rdf:nil
61 Ne683fe9dada54b73aa4e3dc07f23c34e schema:name dimensions_id
62 schema:value pub.1011594790
63 rdf:type schema:PropertyValue
64 Nfe6ae460674f4b119335ae8cd659b805 schema:isbn 978-3-642-14354-0
65 978-3-642-14355-7
66 schema:name Algorithmic Aspects in Information and Management
67 rdf:type schema:Book
68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information and Computing Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
72 schema:name Computation Theory and Mathematics
73 rdf:type schema:DefinedTerm
74 sg:person.015122631215.98 schema:affiliation grid-institutes:grid.412773.4
75 schema:familyName Konno
76 schema:givenName Sayuri
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015122631215.98
78 rdf:type schema:Person
79 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
80 schema:familyName Chen
81 schema:givenName Zhi-Zhong
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
83 rdf:type schema:Person
84 sg:person.015720211615.58 schema:affiliation grid-institutes:grid.412773.4
85 schema:familyName Matsushita
86 schema:givenName Yuki
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015720211615.58
88 rdf:type schema:Person
89 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
90 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
91 rdf:type schema:Organization
 




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


...