Maximum Clique Transversals View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-10-02

AUTHORS

Maw-Shang Chang , Ton Kloks , Chuan-Min Lee

ABSTRACT

A maximum clique transversal set in a graph G is a set S of vertices such that every maximum clique of G contains at least a vertex in S. Clearly, removing a maximum clique transversal set reduces the clique number of a graph. We study algorithmic aspects of the problem, given a graph, to find a maximum clique transversal set of minimum cardinality. We consider the problem for planar graphs and present fixed parameter and approximation results.We also examine some other graph classes: subclasses of chordal graphs such as k-trees, strongly chordal graphs, etc., graphs with few P4s, comparability graphs, and distance hereditary graphs. More... »

PAGES

32-43

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45477-2_5

DOI

http://dx.doi.org/10.1007/3-540-45477-2_5

DIMENSIONS

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


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 Information Engineering, Chung Cheng University, Ming-Shiun, Chiayi 621, Taiwan", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science and Information Engineering, Chung Cheng University, Ming-Shiun, Chiayi 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, Royal Holloway, University of London, SurreyTW20 OEX, Egham, UK", 
          "id": "http://www.grid.ac/institutes/grid.4970.a", 
          "name": [
            "Department of Computer Science, Royal Holloway, University of London, SurreyTW20 OEX, Egham, UK"
          ], 
          "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, Chung Cheng University, Ming-Shiun, Chiayi 621, Taiwan", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science and Information Engineering, Chung Cheng University, Ming-Shiun, Chiayi 621, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lee", 
        "givenName": "Chuan-Min", 
        "id": "sg:person.014674260546.77", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014674260546.77"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-10-02", 
    "datePublishedReg": "2001-10-02", 
    "description": "A maximum clique transversal set in a graph G is a set S of vertices such that every maximum clique of G contains at least a vertex in S. Clearly, removing a maximum clique transversal set reduces the clique number of a graph. We study algorithmic aspects of the problem, given a graph, to find a maximum clique transversal set of minimum cardinality. We consider the problem for planar graphs and present fixed parameter and approximation results.We also examine some other graph classes: subclasses of chordal graphs such as k-trees, strongly chordal graphs, etc., graphs with few P4s, comparability graphs, and distance hereditary graphs.", 
    "editor": [
      {
        "familyName": "Brandst\u00e4dt", 
        "givenName": "Andreas", 
        "type": "Person"
      }, 
      {
        "familyName": "Le", 
        "givenName": "Van Bang", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45477-2_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42707-0", 
        "978-3-540-45477-9"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "transversal set", 
      "approximation results", 
      "algorithmic aspects", 
      "maximum clique", 
      "clique number", 
      "graph", 
      "planar graphs", 
      "graph classes", 
      "problem", 
      "set", 
      "comparability graphs", 
      "vertices", 
      "transversal", 
      "graph G", 
      "chordal graphs", 
      "cardinality", 
      "class", 
      "cliques", 
      "minimum cardinality", 
      "distance hereditary graphs", 
      "parameters", 
      "subclasses", 
      "hereditary graphs", 
      "number", 
      "results", 
      "trees", 
      "aspects", 
      "P4", 
      "maximum clique transversal", 
      "clique transversal", 
      "maximum clique transversal set", 
      "clique transversal set"
    ], 
    "name": "Maximum Clique Transversals", 
    "pagination": "32-43", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019846549"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45477-2_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45477-2_5", 
      "https://app.dimensions.ai/details/publication/pub.1019846549"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:48", 
    "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_160.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45477-2_5"
  }
]
 

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-45477-2_5'

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-45477-2_5'

Turtle is a human-readable linked data format.

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

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-45477-2_5'


 

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

114 TRIPLES      23 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45477-2_5 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nf569581976fa47299725f1cf460fd88c
4 schema:datePublished 2001-10-02
5 schema:datePublishedReg 2001-10-02
6 schema:description A maximum clique transversal set in a graph G is a set S of vertices such that every maximum clique of G contains at least a vertex in S. Clearly, removing a maximum clique transversal set reduces the clique number of a graph. We study algorithmic aspects of the problem, given a graph, to find a maximum clique transversal set of minimum cardinality. We consider the problem for planar graphs and present fixed parameter and approximation results.We also examine some other graph classes: subclasses of chordal graphs such as k-trees, strongly chordal graphs, etc., graphs with few P4s, comparability graphs, and distance hereditary graphs.
7 schema:editor N70e7230d194247edbccbcc7f27c368be
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N72f482adda514f79a465b76ea772d1ea
12 schema:keywords P4
13 algorithmic aspects
14 approximation results
15 aspects
16 cardinality
17 chordal graphs
18 class
19 clique number
20 clique transversal
21 clique transversal set
22 cliques
23 comparability graphs
24 distance hereditary graphs
25 graph
26 graph G
27 graph classes
28 hereditary graphs
29 maximum clique
30 maximum clique transversal
31 maximum clique transversal set
32 minimum cardinality
33 number
34 parameters
35 planar graphs
36 problem
37 results
38 set
39 subclasses
40 transversal
41 transversal set
42 trees
43 vertices
44 schema:name Maximum Clique Transversals
45 schema:pagination 32-43
46 schema:productId N0b1e16c46c9c45fb82edb7937e6605b2
47 Ne8cbacdb2d764065b3ec5e3fadc157e7
48 schema:publisher N2199f6b4db9646c1a289dbb122a02884
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019846549
50 https://doi.org/10.1007/3-540-45477-2_5
51 schema:sdDatePublished 2021-11-01T18:48
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N329c48f42ef54ad3b4eae95b6db9c77e
54 schema:url https://doi.org/10.1007/3-540-45477-2_5
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N0b1e16c46c9c45fb82edb7937e6605b2 schema:name dimensions_id
59 schema:value pub.1019846549
60 rdf:type schema:PropertyValue
61 N137f6350146b4f02b8eb5a6175a92020 schema:familyName Le
62 schema:givenName Van Bang
63 rdf:type schema:Person
64 N2199f6b4db9646c1a289dbb122a02884 schema:name Springer Nature
65 rdf:type schema:Organisation
66 N329c48f42ef54ad3b4eae95b6db9c77e schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N70e7230d194247edbccbcc7f27c368be rdf:first Nb9445f1e55a04029aec40f94437ae1d0
69 rdf:rest Na6b23b8e929d48d1bc27fd83fdc56766
70 N72f482adda514f79a465b76ea772d1ea schema:isbn 978-3-540-42707-0
71 978-3-540-45477-9
72 schema:name Graph-Theoretic Concepts in Computer Science
73 rdf:type schema:Book
74 Na6b23b8e929d48d1bc27fd83fdc56766 rdf:first N137f6350146b4f02b8eb5a6175a92020
75 rdf:rest rdf:nil
76 Nb9445f1e55a04029aec40f94437ae1d0 schema:familyName Brandstädt
77 schema:givenName Andreas
78 rdf:type schema:Person
79 Ndbab7f773edb42688a93270e5aa73ab2 rdf:first sg:person.011052721431.97
80 rdf:rest Nf4154765329e4898810607bf0599c6d7
81 Ne8cbacdb2d764065b3ec5e3fadc157e7 schema:name doi
82 schema:value 10.1007/3-540-45477-2_5
83 rdf:type schema:PropertyValue
84 Nf4154765329e4898810607bf0599c6d7 rdf:first sg:person.014674260546.77
85 rdf:rest rdf:nil
86 Nf569581976fa47299725f1cf460fd88c rdf:first sg:person.013174232477.45
87 rdf:rest Ndbab7f773edb42688a93270e5aa73ab2
88 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
89 schema:name Mathematical Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
92 schema:name Pure Mathematics
93 rdf:type schema:DefinedTerm
94 sg:person.011052721431.97 schema:affiliation grid-institutes:grid.4970.a
95 schema:familyName Kloks
96 schema:givenName Ton
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011052721431.97
98 rdf:type schema:Person
99 sg:person.013174232477.45 schema:affiliation grid-institutes:None
100 schema:familyName Chang
101 schema:givenName Maw-Shang
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
103 rdf:type schema:Person
104 sg:person.014674260546.77 schema:affiliation grid-institutes:None
105 schema:familyName Lee
106 schema:givenName Chuan-Min
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014674260546.77
108 rdf:type schema:Person
109 grid-institutes:None schema:alternateName Department of Computer Science and Information Engineering, Chung Cheng University, Ming-Shiun, Chiayi 621, Taiwan
110 schema:name Department of Computer Science and Information Engineering, Chung Cheng University, Ming-Shiun, Chiayi 621, Taiwan
111 rdf:type schema:Organization
112 grid-institutes:grid.4970.a schema:alternateName Department of Computer Science, Royal Holloway, University of London, SurreyTW20 OEX, Egham, UK
113 schema:name Department of Computer Science, Royal Holloway, University of London, SurreyTW20 OEX, Egham, UK
114 rdf:type schema:Organization
 




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


...