Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Piotr Berman , Martin Fürer , Alexander Zelikovsky

ABSTRACT

The Steiner tree problem in unweighted graphs requires to find a minimum size connected subgraph containing a given subset of nodes (terminals). In this paper we investigate applications of the linear matroid parity algorithm to the Steiner tree problem for two classes of graphs: where the terminals form a vertex cover and where terminals form a dominating set. As all these problems are MAX-SNP-hard, the issue is what approximation can be obtained in polynomial time. The previously best approximation ratio for the first class of graphs (also known as unweighted quasi-bipartite graphs) is ≈ 1.217 (Gröpl et al. [4]) is reduced in this paper to 8/7–1/160≈ 1.137. For the case of graphs where terminals form a dominating set, an approximation ratio of 4/3 is achieved. More... »

PAGES

70-79

Book

TITLE

Computer Science – Theory and Applications

ISBN

978-3-540-34166-6
978-3-540-34168-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11753728_10

DOI

http://dx.doi.org/10.1007/11753728_10

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "F\u00fcrer", 
        "givenName": "Martin", 
        "id": "sg:person.013044430415.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013044430415.38"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, Georgia State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.256304.6", 
          "name": [
            "Computer Science Department, Georgia State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zelikovsky", 
        "givenName": "Alexander", 
        "id": "sg:person.01121041073.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01121041073.51"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "The Steiner tree problem in unweighted graphs requires to find a minimum size connected subgraph containing a given subset of nodes (terminals). In this paper we investigate applications of the linear matroid parity algorithm to the Steiner tree problem for two classes of graphs: where the terminals form a vertex cover and where terminals form a dominating set. As all these problems are MAX-SNP-hard, the issue is what approximation can be obtained in polynomial time. The previously best approximation ratio for the first class of graphs (also known as unweighted quasi-bipartite graphs) is \u2248 1.217 (Gr\u00f6pl et al. [4]) is reduced in this paper to 8/7\u20131/160\u2248 1.137. For the case of graphs where terminals form a dominating set, an approximation ratio of 4/3 is achieved.", 
    "editor": [
      {
        "familyName": "Grigoriev", 
        "givenName": "Dima", 
        "type": "Person"
      }, 
      {
        "familyName": "Harrison", 
        "givenName": "John", 
        "type": "Person"
      }, 
      {
        "familyName": "Hirsch", 
        "givenName": "Edward A.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11753728_10", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-34166-6", 
        "978-3-540-34168-0"
      ], 
      "name": "Computer Science \u2013 Theory and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "Steiner tree problem", 
      "approximation ratio", 
      "parity algorithm", 
      "case of graphs", 
      "class of graphs", 
      "tree problem", 
      "best approximation ratio", 
      "dominating set", 
      "vertex cover", 
      "unweighted graphs", 
      "subset of nodes", 
      "polynomial time", 
      "graph", 
      "MAX SNP", 
      "Steiner tree", 
      "first class", 
      "problem", 
      "minimum size", 
      "algorithm", 
      "approximation", 
      "class", 
      "subgraphs", 
      "set", 
      "applications", 
      "nodes", 
      "subset", 
      "cases", 
      "terminals", 
      "ratio", 
      "size", 
      "time", 
      "trees", 
      "issues", 
      "cover", 
      "paper"
    ], 
    "name": "Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees", 
    "pagination": "70-79", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039297650"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11753728_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11753728_10", 
      "https://app.dimensions.ai/details/publication/pub.1039297650"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_312.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11753728_10"
  }
]
 

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/11753728_10'

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/11753728_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11753728_10'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11753728_10'


 

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

121 TRIPLES      22 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11753728_10 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N3f71076c108c44e49be669e00e1fca26
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description The Steiner tree problem in unweighted graphs requires to find a minimum size connected subgraph containing a given subset of nodes (terminals). In this paper we investigate applications of the linear matroid parity algorithm to the Steiner tree problem for two classes of graphs: where the terminals form a vertex cover and where terminals form a dominating set. As all these problems are MAX-SNP-hard, the issue is what approximation can be obtained in polynomial time. The previously best approximation ratio for the first class of graphs (also known as unweighted quasi-bipartite graphs) is ≈ 1.217 (Gröpl et al. [4]) is reduced in this paper to 8/7–1/160≈ 1.137. For the case of graphs where terminals form a dominating set, an approximation ratio of 4/3 is achieved.
7 schema:editor N987388f16aad4a76ad4d57d9e46ccfc8
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nb58fe044613f447fb81b12fb0d8b124c
11 schema:keywords MAX SNP
12 Steiner tree
13 Steiner tree problem
14 algorithm
15 applications
16 approximation
17 approximation ratio
18 best approximation ratio
19 case of graphs
20 cases
21 class
22 class of graphs
23 cover
24 dominating set
25 first class
26 graph
27 issues
28 minimum size
29 nodes
30 paper
31 parity algorithm
32 polynomial time
33 problem
34 ratio
35 set
36 size
37 subgraphs
38 subset
39 subset of nodes
40 terminals
41 time
42 tree problem
43 trees
44 unweighted graphs
45 vertex cover
46 schema:name Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees
47 schema:pagination 70-79
48 schema:productId Ne8689c3770cd40e297b4a16b9cf61d54
49 Nf7770b50df49464f9c20f5d75dc10ac1
50 schema:publisher Ndb717aa96e7e471f872336ccd4678848
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039297650
52 https://doi.org/10.1007/11753728_10
53 schema:sdDatePublished 2022-08-04T17:18
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher Ncf10593670f94b36ab3707de45ad53bf
56 schema:url https://doi.org/10.1007/11753728_10
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N328a4217b6524955962e9a7403be0775 rdf:first sg:person.013044430415.38
61 rdf:rest Na07f49dbb4264315b1e64d5e0c213d5e
62 N3f71076c108c44e49be669e00e1fca26 rdf:first sg:person.01274506210.27
63 rdf:rest N328a4217b6524955962e9a7403be0775
64 N60695b693d8745e3867c9eb3b4488688 schema:familyName Harrison
65 schema:givenName John
66 rdf:type schema:Person
67 N68003904f3914510a4d7c43093ede8f3 schema:familyName Hirsch
68 schema:givenName Edward A.
69 rdf:type schema:Person
70 N6f495b2f228e48c1b49c3f7aa6cdc229 rdf:first N68003904f3914510a4d7c43093ede8f3
71 rdf:rest rdf:nil
72 N8f1ccf6793c34fb7a49026a06707a89f rdf:first N60695b693d8745e3867c9eb3b4488688
73 rdf:rest N6f495b2f228e48c1b49c3f7aa6cdc229
74 N987388f16aad4a76ad4d57d9e46ccfc8 rdf:first Ne5a08ec1dd0b47abbcae698fe6a3d6ce
75 rdf:rest N8f1ccf6793c34fb7a49026a06707a89f
76 Na07f49dbb4264315b1e64d5e0c213d5e rdf:first sg:person.01121041073.51
77 rdf:rest rdf:nil
78 Nb58fe044613f447fb81b12fb0d8b124c schema:isbn 978-3-540-34166-6
79 978-3-540-34168-0
80 schema:name Computer Science – Theory and Applications
81 rdf:type schema:Book
82 Ncf10593670f94b36ab3707de45ad53bf schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 Ndb717aa96e7e471f872336ccd4678848 schema:name Springer Nature
85 rdf:type schema:Organisation
86 Ne5a08ec1dd0b47abbcae698fe6a3d6ce schema:familyName Grigoriev
87 schema:givenName Dima
88 rdf:type schema:Person
89 Ne8689c3770cd40e297b4a16b9cf61d54 schema:name dimensions_id
90 schema:value pub.1039297650
91 rdf:type schema:PropertyValue
92 Nf7770b50df49464f9c20f5d75dc10ac1 schema:name doi
93 schema:value 10.1007/11753728_10
94 rdf:type schema:PropertyValue
95 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
96 schema:name Mathematical Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
99 schema:name Pure Mathematics
100 rdf:type schema:DefinedTerm
101 sg:person.01121041073.51 schema:affiliation grid-institutes:grid.256304.6
102 schema:familyName Zelikovsky
103 schema:givenName Alexander
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01121041073.51
105 rdf:type schema:Person
106 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
107 schema:familyName Berman
108 schema:givenName Piotr
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
110 rdf:type schema:Person
111 sg:person.013044430415.38 schema:affiliation grid-institutes:grid.29857.31
112 schema:familyName Fürer
113 schema:givenName Martin
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013044430415.38
115 rdf:type schema:Person
116 grid-institutes:grid.256304.6 schema:alternateName Computer Science Department, Georgia State University, USA
117 schema:name Computer Science Department, Georgia State University, USA
118 rdf:type schema:Organization
119 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University, USA
120 schema:name Department of Computer Science and Engineering, Pennsylvania State University, USA
121 rdf:type schema:Organization
 




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


...