The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1999

AUTHORS

Piotr Berman , Andrew B. Kahng , Devendra Vidhani , Alexander Zelikovsky

ABSTRACT

Given a graph G with weighted edges, and a subset of nodes T, the T-join problem asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A iff u ∈ T. We describe the applications of the T-join problem in sparse graphs to the phase assignment problem in VLSI mask layout and to conformal refinement of finite element meshes. We suggest a practical algorithm for the Tjoin problem. In sparse graphs, this algorithm is faster than previously known methods. Computational experience with industrial VLSI layout benchmarks shows the advantages of the new algorithm. More... »

PAGES

25-36

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48447-7_3

DOI

http://dx.doi.org/10.1007/3-540-48447-7_3

DIMENSIONS

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


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": "Dept. of Computer Science and Engineering, Pennsylvania State University, 16802-6106, University Park, PA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Dept. of Computer Science and Engineering, Pennsylvania State University, 16802-6106, University Park, PA"
          ], 
          "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, University of California at Los Angeles, 90095-1596, Los Angeles, CA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "Department of Computer Science, University of California at Los Angeles, 90095-1596, Los Angeles, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kahng", 
        "givenName": "Andrew B.", 
        "id": "sg:person.013652717041.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013652717041.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of California at Los Angeles, 90095-1596, Los Angeles, CA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "Department of Computer Science, University of California at Los Angeles, 90095-1596, Los Angeles, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vidhani", 
        "givenName": "Devendra", 
        "id": "sg:person.015720423514.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015720423514.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Georgia State University, University Plaza, 30303, Atlanta, GA", 
          "id": "http://www.grid.ac/institutes/grid.256304.6", 
          "name": [
            "Department of Computer Science, Georgia State University, University Plaza, 30303, Atlanta, GA"
          ], 
          "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": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "Given a graph G with weighted edges, and a subset of nodes T, the T-join problem asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A iff u \u2208 T. We describe the applications of the T-join problem in sparse graphs to the phase assignment problem in VLSI mask layout and to conformal refinement of finite element meshes. We suggest a practical algorithm for the Tjoin problem. In sparse graphs, this algorithm is faster than previously known methods. Computational experience with industrial VLSI layout benchmarks shows the advantages of the new algorithm.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Gupta", 
        "givenName": "Arvind", 
        "type": "Person"
      }, 
      {
        "familyName": "Tamassia", 
        "givenName": "Roberto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48447-7_3", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66279-2", 
        "978-3-540-48447-9"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "T-join problem", 
      "sparse graphs", 
      "assignment problem", 
      "minimum weight edge", 
      "finite element mesh", 
      "computational experience", 
      "weighted edges", 
      "node t", 
      "graph G", 
      "practical algorithm", 
      "odd number", 
      "element mesh", 
      "graph", 
      "new algorithm", 
      "weight edges", 
      "algorithm", 
      "problem", 
      "node u", 
      "edge", 
      "mask layout", 
      "mesh", 
      "applications", 
      "layout", 
      "benchmarks", 
      "number", 
      "advantages", 
      "subset", 
      "refinement", 
      "experience", 
      "method"
    ], 
    "name": "The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout", 
    "pagination": "25-36", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022260568"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48447-7_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48447-7_3", 
      "https://app.dimensions.ai/details/publication/pub.1022260568"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:22", 
    "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_416.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48447-7_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/3-540-48447-7_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/3-540-48447-7_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48447-7_3'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48447-7_3'


 

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

131 TRIPLES      22 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48447-7_3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5577265679b54fbabe59aab666740db6
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 schema:description Given a graph G with weighted edges, and a subset of nodes T, the T-join problem asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A iff u ∈ T. We describe the applications of the T-join problem in sparse graphs to the phase assignment problem in VLSI mask layout and to conformal refinement of finite element meshes. We suggest a practical algorithm for the Tjoin problem. In sparse graphs, this algorithm is faster than previously known methods. Computational experience with industrial VLSI layout benchmarks shows the advantages of the new algorithm.
7 schema:editor N98621c5ced8547169ce2dc89abbf5a2e
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N7a71030cfc9843e38eacce5377a553cd
11 schema:keywords T-join problem
12 advantages
13 algorithm
14 applications
15 assignment problem
16 benchmarks
17 computational experience
18 edge
19 element mesh
20 experience
21 finite element mesh
22 graph
23 graph G
24 layout
25 mask layout
26 mesh
27 method
28 minimum weight edge
29 new algorithm
30 node t
31 node u
32 number
33 odd number
34 practical algorithm
35 problem
36 refinement
37 sparse graphs
38 subset
39 weight edges
40 weighted edges
41 schema:name The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout
42 schema:pagination 25-36
43 schema:productId N665ab6f554144a50b933a217d9e648a6
44 N8c0484c5ba9942bf8ad6a28070827560
45 schema:publisher N740bfdd315944cb8b9d36526f1340729
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022260568
47 https://doi.org/10.1007/3-540-48447-7_3
48 schema:sdDatePublished 2022-08-04T17:22
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher Ned9d8f10f195481ab8576d4dac8ba710
51 schema:url https://doi.org/10.1007/3-540-48447-7_3
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N04f635e0c37b46c798c335a42eb10615 schema:familyName Sack
56 schema:givenName Jörg-Rüdiger
57 rdf:type schema:Person
58 N157bbd306e8045be86df04b95f7bfa47 rdf:first Nb43715baa20d4833a110649d1077cbaf
59 rdf:rest Nf23422737f93487a81ff7981434f08d2
60 N3670bd1f8a224e8d94d08ce74ea11a5d rdf:first sg:person.015720423514.08
61 rdf:rest Nee9fbc81b1f4477d883185e4f0eb26aa
62 N468f79697c5547baa836cf6f2f3862ae schema:familyName Dehne
63 schema:givenName Frank
64 rdf:type schema:Person
65 N5577265679b54fbabe59aab666740db6 rdf:first sg:person.01274506210.27
66 rdf:rest Nf667bd9a9378470a8d1ea590bb9805a3
67 N665ab6f554144a50b933a217d9e648a6 schema:name dimensions_id
68 schema:value pub.1022260568
69 rdf:type schema:PropertyValue
70 N740bfdd315944cb8b9d36526f1340729 schema:name Springer Nature
71 rdf:type schema:Organisation
72 N7a71030cfc9843e38eacce5377a553cd schema:isbn 978-3-540-48447-9
73 978-3-540-66279-2
74 schema:name Algorithms and Data Structures
75 rdf:type schema:Book
76 N8c0484c5ba9942bf8ad6a28070827560 schema:name doi
77 schema:value 10.1007/3-540-48447-7_3
78 rdf:type schema:PropertyValue
79 N958ca9e661294e0bb486c3996fd530be schema:familyName Tamassia
80 schema:givenName Roberto
81 rdf:type schema:Person
82 N98621c5ced8547169ce2dc89abbf5a2e rdf:first N468f79697c5547baa836cf6f2f3862ae
83 rdf:rest Nc57f102f0dcb4735a3f0637529eb5c6e
84 Nb43715baa20d4833a110649d1077cbaf schema:familyName Gupta
85 schema:givenName Arvind
86 rdf:type schema:Person
87 Nc57f102f0dcb4735a3f0637529eb5c6e rdf:first N04f635e0c37b46c798c335a42eb10615
88 rdf:rest N157bbd306e8045be86df04b95f7bfa47
89 Ned9d8f10f195481ab8576d4dac8ba710 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 Nee9fbc81b1f4477d883185e4f0eb26aa rdf:first sg:person.01121041073.51
92 rdf:rest rdf:nil
93 Nf23422737f93487a81ff7981434f08d2 rdf:first N958ca9e661294e0bb486c3996fd530be
94 rdf:rest rdf:nil
95 Nf667bd9a9378470a8d1ea590bb9805a3 rdf:first sg:person.013652717041.62
96 rdf:rest N3670bd1f8a224e8d94d08ce74ea11a5d
97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
98 schema:name Information and Computing Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
101 schema:name Computation Theory and Mathematics
102 rdf:type schema:DefinedTerm
103 sg:person.01121041073.51 schema:affiliation grid-institutes:grid.256304.6
104 schema:familyName Zelikovsky
105 schema:givenName Alexander
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01121041073.51
107 rdf:type schema:Person
108 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
109 schema:familyName Berman
110 schema:givenName Piotr
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
112 rdf:type schema:Person
113 sg:person.013652717041.62 schema:affiliation grid-institutes:grid.19006.3e
114 schema:familyName Kahng
115 schema:givenName Andrew B.
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013652717041.62
117 rdf:type schema:Person
118 sg:person.015720423514.08 schema:affiliation grid-institutes:grid.19006.3e
119 schema:familyName Vidhani
120 schema:givenName Devendra
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015720423514.08
122 rdf:type schema:Person
123 grid-institutes:grid.19006.3e schema:alternateName Department of Computer Science, University of California at Los Angeles, 90095-1596, Los Angeles, CA
124 schema:name Department of Computer Science, University of California at Los Angeles, 90095-1596, Los Angeles, CA
125 rdf:type schema:Organization
126 grid-institutes:grid.256304.6 schema:alternateName Department of Computer Science, Georgia State University, University Plaza, 30303, Atlanta, GA
127 schema:name Department of Computer Science, Georgia State University, University Plaza, 30303, Atlanta, GA
128 rdf:type schema:Organization
129 grid-institutes:grid.29857.31 schema:alternateName Dept. of Computer Science and Engineering, Pennsylvania State University, 16802-6106, University Park, PA
130 schema:name Dept. of Computer Science and Engineering, Pennsylvania State University, 16802-6106, University Park, PA
131 rdf:type schema:Organization
 




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


...