An Approximation Algorithm for the Minimum Co-Path Set Problem View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-01-21

AUTHORS

Zhi-Zhong Chen, Guohui Lin, Lusheng Wang

ABSTRACT

We present an approximation algorithm for the problem of finding a minimum set of edges in a given graph G whose removal from G leaves a graph in which each connected component is a path. It achieves a 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 {10}{7}$\end{document} and runs in O(n1.5) time, where n is the number of vertices in the input graph. The previously best approximation algorithm for this problem achieves a ratio of 2 and runs in O(n2) time. More... »

PAGES

969-986

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-010-9389-x

DOI

http://dx.doi.org/10.1007/s00453-010-9389-x

DIMENSIONS

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


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 Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada", 
          "id": "http://www.grid.ac/institutes/grid.17089.37", 
          "name": [
            "Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Guohui", 
        "id": "sg:person.01130357621.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.35030.35", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Lusheng", 
        "id": "sg:person.01105113721.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s00453-002-1001-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039324442", 
          "https://doi.org/10.1007/s00453-002-1001-6"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010-01-21", 
    "datePublishedReg": "2010-01-21", 
    "description": "We present an approximation algorithm for the problem of finding a minimum set of edges in a given graph G whose removal from G leaves a graph in which each connected component is a path. It achieves a ratio of \n\\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 {10}{7}$\\end{document} \nand runs in O(n1.5) time, where n is the number of vertices in the input graph. The previously best approximation algorithm for this problem achieves a ratio of\u00a02 and runs in O(n2) time.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-010-9389-x", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.5990357", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "60"
      }
    ], 
    "keywords": [
      "approximation algorithm", 
      "best approximation algorithm", 
      "number of vertices", 
      "graph G", 
      "input graph", 
      "set problem", 
      "graph", 
      "algorithm", 
      "problem", 
      "minimum set", 
      "vertices", 
      "set", 
      "edge", 
      "path", 
      "ratio", 
      "run", 
      "time", 
      "number", 
      "components", 
      "removal"
    ], 
    "name": "An Approximation Algorithm for the Minimum Co-Path Set Problem", 
    "pagination": "969-986", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037254527"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-010-9389-x"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-010-9389-x", 
      "https://app.dimensions.ai/details/publication/pub.1037254527"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-05-10T10:02", 
    "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/article/article_503.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-010-9389-x"
  }
]
 

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/s00453-010-9389-x'

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/s00453-010-9389-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-010-9389-x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-010-9389-x'


 

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

104 TRIPLES      22 PREDICATES      46 URIs      37 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-010-9389-x schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ncf157590ea604c4d9fdaa01cd0e23e19
4 schema:citation sg:pub.10.1007/s00453-002-1001-6
5 schema:datePublished 2010-01-21
6 schema:datePublishedReg 2010-01-21
7 schema:description We present an approximation algorithm for the problem of finding a minimum set of edges in a given graph G whose removal from G leaves a graph in which each connected component is a path. It achieves a 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 {10}{7}$\end{document} and runs in O(n1.5) time, where n is the number of vertices in the input graph. The previously best approximation algorithm for this problem achieves a ratio of 2 and runs in O(n2) time.
8 schema:genre article
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N6050bd1040ff4d55892ebadaeb3d5956
12 N72c93a9de8c941ce80d5d1a27534793e
13 sg:journal.1047644
14 schema:keywords algorithm
15 approximation algorithm
16 best approximation algorithm
17 components
18 edge
19 graph
20 graph G
21 input graph
22 minimum set
23 number
24 number of vertices
25 path
26 problem
27 ratio
28 removal
29 run
30 set
31 set problem
32 time
33 vertices
34 schema:name An Approximation Algorithm for the Minimum Co-Path Set Problem
35 schema:pagination 969-986
36 schema:productId N0a8a6929c87d4a708b84ef0f6caf17ef
37 N92c476d3c065496787105bce40d20509
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037254527
39 https://doi.org/10.1007/s00453-010-9389-x
40 schema:sdDatePublished 2022-05-10T10:02
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher Nde910dfa4d4045c39c640e2819d12e05
43 schema:url https://doi.org/10.1007/s00453-010-9389-x
44 sgo:license sg:explorer/license/
45 sgo:sdDataset articles
46 rdf:type schema:ScholarlyArticle
47 N0a8a6929c87d4a708b84ef0f6caf17ef schema:name doi
48 schema:value 10.1007/s00453-010-9389-x
49 rdf:type schema:PropertyValue
50 N6050bd1040ff4d55892ebadaeb3d5956 schema:issueNumber 4
51 rdf:type schema:PublicationIssue
52 N72c93a9de8c941ce80d5d1a27534793e schema:volumeNumber 60
53 rdf:type schema:PublicationVolume
54 N92c476d3c065496787105bce40d20509 schema:name dimensions_id
55 schema:value pub.1037254527
56 rdf:type schema:PropertyValue
57 Ncf157590ea604c4d9fdaa01cd0e23e19 rdf:first sg:person.015654265661.98
58 rdf:rest Ne4ad78d7ff5340b99613380874ad7eab
59 Nde910dfa4d4045c39c640e2819d12e05 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 Ne4ad78d7ff5340b99613380874ad7eab rdf:first sg:person.01130357621.02
62 rdf:rest Nf875dd1b2fd94ca4ae2f02f39f3ca1b1
63 Nf875dd1b2fd94ca4ae2f02f39f3ca1b1 rdf:first sg:person.01105113721.52
64 rdf:rest rdf:nil
65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
66 schema:name Information and Computing Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
69 schema:name Computation Theory and Mathematics
70 rdf:type schema:DefinedTerm
71 sg:grant.5990357 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-010-9389-x
72 rdf:type schema:MonetaryGrant
73 sg:journal.1047644 schema:issn 0178-4617
74 1432-0541
75 schema:name Algorithmica
76 schema:publisher Springer Nature
77 rdf:type schema:Periodical
78 sg:person.01105113721.52 schema:affiliation grid-institutes:grid.35030.35
79 schema:familyName Wang
80 schema:givenName Lusheng
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
82 rdf:type schema:Person
83 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.17089.37
84 schema:familyName Lin
85 schema:givenName Guohui
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
87 rdf:type schema:Person
88 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
89 schema:familyName Chen
90 schema:givenName Zhi-Zhong
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
92 rdf:type schema:Person
93 sg:pub.10.1007/s00453-002-1001-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039324442
94 https://doi.org/10.1007/s00453-002-1001-6
95 rdf:type schema:CreativeWork
96 grid-institutes:grid.17089.37 schema:alternateName Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada
97 schema:name Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada
98 rdf:type schema:Organization
99 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong
100 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong
101 rdf:type schema:Organization
102 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
103 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
104 rdf:type schema:Organization
 




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


...