On Maximum Symmetric Subgraphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001

AUTHORS

Ho-Lin Chen , Hsueh-I. Lu , Hsu-Chun Yen

ABSTRACT

Let G be an n-node graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting edges, and contracting edges. This NP-complete problem arises naturally from the objective of drawing G as symmetrically as possible. We show that its tractability for the special cases of G being a plane graph, an ordered tree, and an unordered tree, depends on the type of operations used to obtain H from G. Moreover, we give an O(log n)-approximation algorithm for the intractable case that H is obtained from a tree G by contracting edges. As a by-product, we give an O(log n)-approximation algorithm for an NP-complete edit-distance problem. More... »

PAGES

372-383

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44541-2_35

DOI

http://dx.doi.org/10.1007/3-540-44541-2_35

DIMENSIONS

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


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 Electrical Engineering, National Taiwan University, 106, Taipei, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Electrical Engineering, National Taiwan University, 106, Taipei, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Ho-Lin", 
        "id": "sg:person.012704570265.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012704570265.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Information Science, Academia Sinica, 115, Taipei, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "Institute of Information Science, Academia Sinica, 115, Taipei, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I.", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Electrical Engineering, National Taiwan University, 106, Taipei, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Electrical Engineering, National Taiwan University, 106, Taipei, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yen", 
        "givenName": "Hsu-Chun", 
        "id": "sg:person.015077575457.09", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015077575457.09"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001", 
    "datePublishedReg": "2001-01-01", 
    "description": "Let G be an n-node graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting edges, and contracting edges. This NP-complete problem arises naturally from the objective of drawing G as symmetrically as possible. We show that its tractability for the special cases of G being a plane graph, an ordered tree, and an unordered tree, depends on the type of operations used to obtain H from G. Moreover, we give an O(log n)-approximation algorithm for the intractable case that H is obtained from a tree G by contracting edges. As a by-product, we give an O(log n)-approximation algorithm for an NP-complete edit-distance problem.", 
    "editor": [
      {
        "familyName": "Marks", 
        "givenName": "Joe", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44541-2_35", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-41554-1", 
        "978-3-540-44541-8"
      ], 
      "name": "Graph Drawing", 
      "type": "Book"
    }, 
    "keywords": [
      "approximation algorithm", 
      "NP-complete problem", 
      "graph H", 
      "special case", 
      "plane graph", 
      "node graph", 
      "contracting edges", 
      "edit distance problem", 
      "graph", 
      "problem", 
      "algorithm", 
      "tree G", 
      "edge", 
      "tractability", 
      "subgraphs", 
      "cases", 
      "nodes", 
      "unordered trees", 
      "trees", 
      "operation", 
      "Moreover", 
      "objective", 
      "type of operation", 
      "types", 
      "intractable cases", 
      "products"
    ], 
    "name": "On Maximum Symmetric Subgraphs", 
    "pagination": "372-383", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005133230"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44541-2_35"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44541-2_35", 
      "https://app.dimensions.ai/details/publication/pub.1005133230"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:54", 
    "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_49.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44541-2_35"
  }
]
 

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-44541-2_35'

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-44541-2_35'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44541-2_35'

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-44541-2_35'


 

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

103 TRIPLES      23 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44541-2_35 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ncfb69d708e1c41b7a4c2d5a95eb1847e
4 schema:datePublished 2001
5 schema:datePublishedReg 2001-01-01
6 schema:description Let G be an n-node graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting edges, and contracting edges. This NP-complete problem arises naturally from the objective of drawing G as symmetrically as possible. We show that its tractability for the special cases of G being a plane graph, an ordered tree, and an unordered tree, depends on the type of operations used to obtain H from G. Moreover, we give an O(log n)-approximation algorithm for the intractable case that H is obtained from a tree G by contracting edges. As a by-product, we give an O(log n)-approximation algorithm for an NP-complete edit-distance problem.
7 schema:editor N80d726b520c045c1a6952481c8948cba
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3d295887c48c46d895fe2eb53afffb41
12 schema:keywords Moreover
13 NP-complete problem
14 algorithm
15 approximation algorithm
16 cases
17 contracting edges
18 edge
19 edit distance problem
20 graph
21 graph H
22 intractable cases
23 node graph
24 nodes
25 objective
26 operation
27 plane graph
28 problem
29 products
30 special case
31 subgraphs
32 tractability
33 tree G
34 trees
35 type of operation
36 types
37 unordered trees
38 schema:name On Maximum Symmetric Subgraphs
39 schema:pagination 372-383
40 schema:productId N04c76b9d0a8e46c6991ba082ffc17b4f
41 N4c6eaef1f6c546c9b54b4724490510f1
42 schema:publisher N4b79438d9e55419eafcee3d693800463
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005133230
44 https://doi.org/10.1007/3-540-44541-2_35
45 schema:sdDatePublished 2022-05-10T10:54
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N5938a0b2bd944eaa8382cf1018e0e6cf
48 schema:url https://doi.org/10.1007/3-540-44541-2_35
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N04c76b9d0a8e46c6991ba082ffc17b4f schema:name dimensions_id
53 schema:value pub.1005133230
54 rdf:type schema:PropertyValue
55 N0b3d637e65a94a268f5ed16931c2af5c schema:familyName Marks
56 schema:givenName Joe
57 rdf:type schema:Person
58 N2ea55c0befb44ecf8ac89c73d9ed48f5 rdf:first sg:person.015077575457.09
59 rdf:rest rdf:nil
60 N3d295887c48c46d895fe2eb53afffb41 schema:isbn 978-3-540-41554-1
61 978-3-540-44541-8
62 schema:name Graph Drawing
63 rdf:type schema:Book
64 N4b79438d9e55419eafcee3d693800463 schema:name Springer Nature
65 rdf:type schema:Organisation
66 N4c6eaef1f6c546c9b54b4724490510f1 schema:name doi
67 schema:value 10.1007/3-540-44541-2_35
68 rdf:type schema:PropertyValue
69 N5938a0b2bd944eaa8382cf1018e0e6cf schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N80d726b520c045c1a6952481c8948cba rdf:first N0b3d637e65a94a268f5ed16931c2af5c
72 rdf:rest rdf:nil
73 Ncfb69d708e1c41b7a4c2d5a95eb1847e rdf:first sg:person.012704570265.60
74 rdf:rest Nd231383df3a84990876ce95c5b94ba84
75 Nd231383df3a84990876ce95c5b94ba84 rdf:first sg:person.013345515575.46
76 rdf:rest N2ea55c0befb44ecf8ac89c73d9ed48f5
77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
78 schema:name Information and Computing Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
81 schema:name Computation Theory and Mathematics
82 rdf:type schema:DefinedTerm
83 sg:person.012704570265.60 schema:affiliation grid-institutes:grid.19188.39
84 schema:familyName Chen
85 schema:givenName Ho-Lin
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012704570265.60
87 rdf:type schema:Person
88 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.28665.3f
89 schema:familyName Lu
90 schema:givenName Hsueh-I.
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
92 rdf:type schema:Person
93 sg:person.015077575457.09 schema:affiliation grid-institutes:grid.19188.39
94 schema:familyName Yen
95 schema:givenName Hsu-Chun
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015077575457.09
97 rdf:type schema:Person
98 grid-institutes:grid.19188.39 schema:alternateName Department of Electrical Engineering, National Taiwan University, 106, Taipei, Taiwan, R.O.C.
99 schema:name Department of Electrical Engineering, National Taiwan University, 106, Taipei, Taiwan, R.O.C.
100 rdf:type schema:Organization
101 grid-institutes:grid.28665.3f schema:alternateName Institute of Information Science, Academia Sinica, 115, Taipei, Taiwan, R.O.C.
102 schema:name Institute of Information Science, Academia Sinica, 115, Taipei, Taiwan, R.O.C.
103 rdf:type schema:Organization
 




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


...