An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007-01-01

AUTHORS

Zhi-Zhong Chen , Ruka Tanahashi

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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{468}{575}$\end{document}. This improves on the previous best (trivial) ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{4}{5}$\end{document}. More... »

PAGES

27-36

Book

TITLE

Algorithmic Aspects in Information and Management

ISBN

978-3-540-72868-9
978-3-540-72870-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-72870-2_3

DOI

http://dx.doi.org/10.1007/978-3-540-72870-2_3

DIMENSIONS

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


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, Saitama 350-0394, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, 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, Saitama 350-0394, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tanahashi", 
        "givenName": "Ruka", 
        "id": "sg:person.014101003752.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014101003752.39"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-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 \\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{468}{575}$\\end{document}. This improves on the previous best (trivial) ratio of \\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{4}{5}$\\end{document}.", 
    "editor": [
      {
        "familyName": "Kao", 
        "givenName": "Ming-Yang", 
        "type": "Person"
      }, 
      {
        "familyName": "Li", 
        "givenName": "Xiang-Yang", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-72870-2_3", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-72868-9", 
        "978-3-540-72870-2"
      ], 
      "name": "Algorithmic Aspects in Information and Management", 
      "type": "Book"
    }, 
    "keywords": [
      "approximation algorithm", 
      "simple graph", 
      "polynomial-time approximation algorithm", 
      "improved approximation algorithms", 
      "approximation ratio", 
      "maximum edge", 
      "previous best ratio", 
      "graph", 
      "algorithm", 
      "edge", 
      "best ratio", 
      "ratio", 
      "color"
    ], 
    "name": "An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs", 
    "pagination": "27-36", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025761241"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-72870-2_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-72870-2_3", 
      "https://app.dimensions.ai/details/publication/pub.1025761241"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:38", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_152.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-72870-2_3"
  }
]
 

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-72870-2_3'

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-72870-2_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-72870-2_3'

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-72870-2_3'


 

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

85 TRIPLES      23 PREDICATES      38 URIs      31 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-72870-2_3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N099277f7e0aa4c4683ee6472898c79d1
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{468}{575}$\end{document}. This improves on the previous best (trivial) ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{4}{5}$\end{document}.
7 schema:editor N63d3788094234571b3628558351ae9d4
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N1ed8ee74cd8a4372bf3f9efbe7eaa96c
12 schema:keywords algorithm
13 approximation algorithm
14 approximation ratio
15 best ratio
16 color
17 edge
18 graph
19 improved approximation algorithms
20 maximum edge
21 polynomial-time approximation algorithm
22 previous best ratio
23 ratio
24 simple graph
25 schema:name An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs
26 schema:pagination 27-36
27 schema:productId N2d9c4e6f1d354b988989d174bd3906f6
28 Na58cb5d6864c4a558634ef8728ef6203
29 schema:publisher N4086830fe7c9418cbf931ef3716ec5e0
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025761241
31 https://doi.org/10.1007/978-3-540-72870-2_3
32 schema:sdDatePublished 2022-05-10T10:38
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N350feb4b943f4aa591dd757873e3a968
35 schema:url https://doi.org/10.1007/978-3-540-72870-2_3
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N099277f7e0aa4c4683ee6472898c79d1 rdf:first sg:person.015654265661.98
40 rdf:rest N713c9534af834ea198bdb76c62cf4ce9
41 N1ed8ee74cd8a4372bf3f9efbe7eaa96c schema:isbn 978-3-540-72868-9
42 978-3-540-72870-2
43 schema:name Algorithmic Aspects in Information and Management
44 rdf:type schema:Book
45 N2d9c4e6f1d354b988989d174bd3906f6 schema:name dimensions_id
46 schema:value pub.1025761241
47 rdf:type schema:PropertyValue
48 N350feb4b943f4aa591dd757873e3a968 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 N4086830fe7c9418cbf931ef3716ec5e0 schema:name Springer Nature
51 rdf:type schema:Organisation
52 N63d3788094234571b3628558351ae9d4 rdf:first N9fa965eccad14e11bdbb07b319ee849a
53 rdf:rest N96f5242f8e224651a818afd91744eabc
54 N713c9534af834ea198bdb76c62cf4ce9 rdf:first sg:person.014101003752.39
55 rdf:rest rdf:nil
56 N96f5242f8e224651a818afd91744eabc rdf:first N9bb47c72d0c34520805b91b90edf9bae
57 rdf:rest rdf:nil
58 N9bb47c72d0c34520805b91b90edf9bae schema:familyName Li
59 schema:givenName Xiang-Yang
60 rdf:type schema:Person
61 N9fa965eccad14e11bdbb07b319ee849a schema:familyName Kao
62 schema:givenName Ming-Yang
63 rdf:type schema:Person
64 Na58cb5d6864c4a558634ef8728ef6203 schema:name doi
65 schema:value 10.1007/978-3-540-72870-2_3
66 rdf:type schema:PropertyValue
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.014101003752.39 schema:affiliation grid-institutes:grid.412773.4
74 schema:familyName Tanahashi
75 schema:givenName Ruka
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014101003752.39
77 rdf:type schema:Person
78 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
79 schema:familyName Chen
80 schema:givenName Zhi-Zhong
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
82 rdf:type schema:Person
83 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
84 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
85 rdf:type schema:Organization
 




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


...