Ontology type: schema:Chapter Open Access: True
2007-01-01
AUTHORSZhi-Zhong Chen , Ruka Tanahashi
ABSTRACTWe 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... »
PAGES27-36
Algorithmic Aspects in Information and Management
ISBN
978-3-540-72868-9
978-3-540-72870-2
http://scigraph.springernature.com/pub.10.1007/978-3-540-72870-2_3
DOIhttp://dx.doi.org/10.1007/978-3-540-72870-2_3
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1025761241
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
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