Block-Graph Width View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Maw-Shang Chang , Ling-Ju Hung , Ton Kloks , Sheng-Lung Peng

ABSTRACT

The \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document}-width of a class of graphs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document} is defined as follows. A graph G has \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document}-width k if there are k independent sets \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{N}_1,\dots,\mathbb{N}_{\rm \tt k}$\end{document} in G such that G can be embedded into a graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\rm H \in \mathcal{G}}$\end{document} such that for every edge e in H which is not an edge in G, there exists an i such that both endpoints of e are in ℕi. For the class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathfrak{B}$\end{document} of block graphs we show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathfrak{B}$\end{document}-width is NP-complete and we present fixed-parameter algorithms. More... »

PAGES

150-157

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-02017-9_18

DOI

http://dx.doi.org/10.1007/978-3-642-02017-9_18

DIMENSIONS

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


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 Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chia-Yi 621, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chia-Yi 621, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chang", 
        "givenName": "Maw-Shang", 
        "id": "sg:person.013174232477.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chia-Yi 621, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chia-Yi 621, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hung", 
        "givenName": "Ling-Ju", 
        "id": "sg:person.014652573161.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014652573161.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "No Affiliations", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "No Affiliations"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kloks", 
        "givenName": "Ton", 
        "id": "sg:person.011052721431.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011052721431.97"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Shoufeng, Hualien, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.260567.0", 
          "name": [
            "Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Shoufeng, Hualien, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Peng", 
        "givenName": "Sheng-Lung", 
        "id": "sg:person.013531324035.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "The \\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}$\\mathcal{G}$\\end{document}-width of a class of graphs \\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}$\\mathcal{G}$\\end{document} is defined as follows. A graph G has \\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}$\\mathcal{G}$\\end{document}-width k if there are k independent sets \\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}$\\mathbb{N}_1,\\dots,\\mathbb{N}_{\\rm \\tt k}$\\end{document} in G such that G can be embedded into a graph \\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}${\\rm H \\in \\mathcal{G}}$\\end{document} such that for every edge e in H which is not an edge in G, there exists an i such that both endpoints of e are in \u2115i. For the class \\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}$\\mathfrak{B}$\\end{document} of block graphs we show that \\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}$\\mathfrak{B}$\\end{document}-width is NP-complete and we present fixed-parameter algorithms.", 
    "editor": [
      {
        "familyName": "Chen", 
        "givenName": "Jianer", 
        "type": "Person"
      }, 
      {
        "familyName": "Cooper", 
        "givenName": "S. Barry", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-02017-9_18", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-02016-2", 
        "978-3-642-02017-9"
      ], 
      "name": "Theory and Applications of Models of Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "follow", 
      "endpoints", 
      "independent set", 
      "class", 
      "width", 
      "set", 
      "edge e", 
      "edge", 
      "graph G", 
      "algorithm", 
      "graph", 
      "block graphs", 
      "class of graphs", 
      "fixed-parameter algorithm", 
      "present fixed-parameter algorithms", 
      "Block-Graph Width"
    ], 
    "name": "Block-Graph Width", 
    "pagination": "150-157", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029034640"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-02017-9_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-02017-9_18", 
      "https://app.dimensions.ai/details/publication/pub.1029034640"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T19:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_419.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-02017-9_18"
  }
]
 

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/978-3-642-02017-9_18'

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-642-02017-9_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02017-9_18'

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-642-02017-9_18'


 

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

108 TRIPLES      23 PREDICATES      41 URIs      34 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-02017-9_18 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N1b2841d713f64f8490f05d3b7b7bb0df
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description The \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document}-width of a class of graphs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document} is defined as follows. A graph G has \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document}-width k if there are k independent sets \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{N}_1,\dots,\mathbb{N}_{\rm \tt k}$\end{document} in G such that G can be embedded into a graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\rm H \in \mathcal{G}}$\end{document} such that for every edge e in H which is not an edge in G, there exists an i such that both endpoints of e are in ℕi. For the class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathfrak{B}$\end{document} of block graphs we show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathfrak{B}$\end{document}-width is NP-complete and we present fixed-parameter algorithms.
7 schema:editor N38c1c3d073ed4b3aa8828b595851f259
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N6e32be3381af4f80bec5de22726c1ebc
12 schema:keywords Block-Graph Width
13 algorithm
14 block graphs
15 class
16 class of graphs
17 edge
18 edge e
19 endpoints
20 fixed-parameter algorithm
21 follow
22 graph
23 graph G
24 independent set
25 present fixed-parameter algorithms
26 set
27 width
28 schema:name Block-Graph Width
29 schema:pagination 150-157
30 schema:productId N566cb060784043cc81b400250e58e6c1
31 N945b3cd1c1524ad683d24afb2f13c382
32 schema:publisher Nc189c3cdd05143eda196a80352d61e2e
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029034640
34 https://doi.org/10.1007/978-3-642-02017-9_18
35 schema:sdDatePublished 2021-11-01T19:00
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher N5e5178d560b749b3b914803d836c60c3
38 schema:url https://doi.org/10.1007/978-3-642-02017-9_18
39 sgo:license sg:explorer/license/
40 sgo:sdDataset chapters
41 rdf:type schema:Chapter
42 N1b2841d713f64f8490f05d3b7b7bb0df rdf:first sg:person.013174232477.45
43 rdf:rest Ne4e5a83139b84f1f8ffedaa8f2e6bed7
44 N38c1c3d073ed4b3aa8828b595851f259 rdf:first Naddbfd0ae08341a1bea3ad14280b6847
45 rdf:rest Nd94d5fae8f6145baaa19d36f8721bc0f
46 N566cb060784043cc81b400250e58e6c1 schema:name doi
47 schema:value 10.1007/978-3-642-02017-9_18
48 rdf:type schema:PropertyValue
49 N5e5178d560b749b3b914803d836c60c3 schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 N6e1fa9a04880484e85b3401adb120163 rdf:first sg:person.013531324035.31
52 rdf:rest rdf:nil
53 N6e32be3381af4f80bec5de22726c1ebc schema:isbn 978-3-642-02016-2
54 978-3-642-02017-9
55 schema:name Theory and Applications of Models of Computation
56 rdf:type schema:Book
57 N844b6cfe10034f5faee5805b70f0dba3 schema:familyName Cooper
58 schema:givenName S. Barry
59 rdf:type schema:Person
60 N945b3cd1c1524ad683d24afb2f13c382 schema:name dimensions_id
61 schema:value pub.1029034640
62 rdf:type schema:PropertyValue
63 Naddbfd0ae08341a1bea3ad14280b6847 schema:familyName Chen
64 schema:givenName Jianer
65 rdf:type schema:Person
66 Nb9b4bd7f5fa242879b1e77d0a7c346b4 rdf:first sg:person.011052721431.97
67 rdf:rest N6e1fa9a04880484e85b3401adb120163
68 Nc189c3cdd05143eda196a80352d61e2e schema:name Springer Nature
69 rdf:type schema:Organisation
70 Nd94d5fae8f6145baaa19d36f8721bc0f rdf:first N844b6cfe10034f5faee5805b70f0dba3
71 rdf:rest rdf:nil
72 Ne4e5a83139b84f1f8ffedaa8f2e6bed7 rdf:first sg:person.014652573161.60
73 rdf:rest Nb9b4bd7f5fa242879b1e77d0a7c346b4
74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
75 schema:name Information and Computing Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
78 schema:name Computation Theory and Mathematics
79 rdf:type schema:DefinedTerm
80 sg:person.011052721431.97 schema:affiliation grid-institutes:None
81 schema:familyName Kloks
82 schema:givenName Ton
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011052721431.97
84 rdf:type schema:Person
85 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
86 schema:familyName Chang
87 schema:givenName Maw-Shang
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
89 rdf:type schema:Person
90 sg:person.013531324035.31 schema:affiliation grid-institutes:grid.260567.0
91 schema:familyName Peng
92 schema:givenName Sheng-Lung
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31
94 rdf:type schema:Person
95 sg:person.014652573161.60 schema:affiliation grid-institutes:grid.412047.4
96 schema:familyName Hung
97 schema:givenName Ling-Ju
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014652573161.60
99 rdf:type schema:Person
100 grid-institutes:None schema:alternateName No Affiliations
101 schema:name No Affiliations
102 rdf:type schema:Organization
103 grid-institutes:grid.260567.0 schema:alternateName Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Shoufeng, Hualien, Taiwan
104 schema:name Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Shoufeng, Hualien, Taiwan
105 rdf:type schema:Organization
106 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chia-Yi 621, Taiwan
107 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chia-Yi 621, Taiwan
108 rdf:type schema:Organization
 




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


...