Sweeping Graphs with Large Clique Number View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Boting Yang , Danny Dyer , Brian Alspach

ABSTRACT

An open problem in sweeping is the existence of a graph with connected sweep number strictly less than monotonic connected sweep number. We solve this problem by constructing a graph W exhibiting exactly this property. Further, we will examine a new method of constructing graphs that makes proving all such inequalities easier, and offer some new lower bounds on sweep numbers. More... »

PAGES

908-920

References to SciGraph publications

  • 2003. Searching Is Not Jumping in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • Book

    TITLE

    Algorithms and Computation

    ISBN

    978-3-540-24131-7
    978-3-540-30551-4

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-30551-4_77

    DOI

    http://dx.doi.org/10.1007/978-3-540-30551-4_77

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Regina", 
              "id": "https://www.grid.ac/institutes/grid.57926.3f", 
              "name": [
                "Department of Computer Science, University of Regina"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yang", 
            "givenName": "Boting", 
            "id": "sg:person.010020724604.82", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010020724604.82"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Simon Fraser University", 
              "id": "https://www.grid.ac/institutes/grid.61971.38", 
              "name": [
                "Department of Mathematics, Simon Fraser University"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Dyer", 
            "givenName": "Danny", 
            "id": "sg:person.015173770711.52", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015173770711.52"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Regina", 
              "id": "https://www.grid.ac/institutes/grid.57926.3f", 
              "name": [
                "Department of Mathematics and Statistics, University of Regina"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Alspach", 
            "givenName": "Brian", 
            "id": "sg:person.012155470203.67", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012155470203.67"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/151261.151263", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017456454"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-39890-5_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025064061", 
              "https://doi.org/10.1007/978-3-540-39890-5_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-39890-5_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025064061", 
              "https://doi.org/10.1007/978-3-540-39890-5_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(91)90003-h", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033945460"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/42267.42268", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045068727"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "An open problem in sweeping is the existence of a graph with connected sweep number strictly less than monotonic connected sweep number. We solve this problem by constructing a graph W exhibiting exactly this property. Further, we will examine a new method of constructing graphs that makes proving all such inequalities easier, and offer some new lower bounds on sweep numbers.", 
        "editor": [
          {
            "familyName": "Fleischer", 
            "givenName": "Rudolf", 
            "type": "Person"
          }, 
          {
            "familyName": "Trippen", 
            "givenName": "Gerhard", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-30551-4_77", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-24131-7", 
            "978-3-540-30551-4"
          ], 
          "name": "Algorithms and Computation", 
          "type": "Book"
        }, 
        "name": "Sweeping Graphs with Large Clique Number", 
        "pagination": "908-920", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1020618149"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-30551-4_77"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "623e012f91dda9437e19bd1954d1c908b72a834444af9e1be0b9d86a2fa47a4e"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-30551-4_77", 
          "https://app.dimensions.ai/details/publication/pub.1020618149"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:38", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000365_0000000365/records_71707_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-30551-4_77"
      }
    ]
     

    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-540-30551-4_77'

    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-540-30551-4_77'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30551-4_77'

    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-540-30551-4_77'


     

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

    101 TRIPLES      23 PREDICATES      31 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-30551-4_77 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N4b5bcfe564004eb89b82de9889fd28d9
    4 schema:citation sg:pub.10.1007/978-3-540-39890-5_4
    5 https://doi.org/10.1016/0196-6774(91)90003-h
    6 https://doi.org/10.1145/151261.151263
    7 https://doi.org/10.1145/42267.42268
    8 schema:datePublished 2004
    9 schema:datePublishedReg 2004-01-01
    10 schema:description An open problem in sweeping is the existence of a graph with connected sweep number strictly less than monotonic connected sweep number. We solve this problem by constructing a graph W exhibiting exactly this property. Further, we will examine a new method of constructing graphs that makes proving all such inequalities easier, and offer some new lower bounds on sweep numbers.
    11 schema:editor N47d0060052a54429889c9b4d8a5a563a
    12 schema:genre chapter
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N57efe0213cf444f3810a3749392cf552
    16 schema:name Sweeping Graphs with Large Clique Number
    17 schema:pagination 908-920
    18 schema:productId N503c9511af044ec6970c870da9eaa527
    19 N8459b9c95e8148faa13d01030f84cab1
    20 Nc87574c206a140cfb8af6ae68e7b01b9
    21 schema:publisher N101725de8d964bff9f9ddfd36f0739e9
    22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020618149
    23 https://doi.org/10.1007/978-3-540-30551-4_77
    24 schema:sdDatePublished 2019-04-16T08:38
    25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    26 schema:sdPublisher N2c94e630710a40bfa411d0cd42c93600
    27 schema:url https://link.springer.com/10.1007%2F978-3-540-30551-4_77
    28 sgo:license sg:explorer/license/
    29 sgo:sdDataset chapters
    30 rdf:type schema:Chapter
    31 N101725de8d964bff9f9ddfd36f0739e9 schema:location Berlin, Heidelberg
    32 schema:name Springer Berlin Heidelberg
    33 rdf:type schema:Organisation
    34 N2c94e630710a40bfa411d0cd42c93600 schema:name Springer Nature - SN SciGraph project
    35 rdf:type schema:Organization
    36 N2cdc840fb2b344599c175b40f6d3c9c5 rdf:first sg:person.012155470203.67
    37 rdf:rest rdf:nil
    38 N47d0060052a54429889c9b4d8a5a563a rdf:first N52c7793134e6465da42cc93b470e97bb
    39 rdf:rest N64d1ce7e132d4eb9a0426834f5a271ed
    40 N4b5bcfe564004eb89b82de9889fd28d9 rdf:first sg:person.010020724604.82
    41 rdf:rest N8cb999e69399484c92e5b81daed0c9b4
    42 N503c9511af044ec6970c870da9eaa527 schema:name doi
    43 schema:value 10.1007/978-3-540-30551-4_77
    44 rdf:type schema:PropertyValue
    45 N52c7793134e6465da42cc93b470e97bb schema:familyName Fleischer
    46 schema:givenName Rudolf
    47 rdf:type schema:Person
    48 N57efe0213cf444f3810a3749392cf552 schema:isbn 978-3-540-24131-7
    49 978-3-540-30551-4
    50 schema:name Algorithms and Computation
    51 rdf:type schema:Book
    52 N64d1ce7e132d4eb9a0426834f5a271ed rdf:first N99a8b6c9cb9746e98b6f98067f151920
    53 rdf:rest rdf:nil
    54 N8459b9c95e8148faa13d01030f84cab1 schema:name readcube_id
    55 schema:value 623e012f91dda9437e19bd1954d1c908b72a834444af9e1be0b9d86a2fa47a4e
    56 rdf:type schema:PropertyValue
    57 N8cb999e69399484c92e5b81daed0c9b4 rdf:first sg:person.015173770711.52
    58 rdf:rest N2cdc840fb2b344599c175b40f6d3c9c5
    59 N99a8b6c9cb9746e98b6f98067f151920 schema:familyName Trippen
    60 schema:givenName Gerhard
    61 rdf:type schema:Person
    62 Nc87574c206a140cfb8af6ae68e7b01b9 schema:name dimensions_id
    63 schema:value pub.1020618149
    64 rdf:type schema:PropertyValue
    65 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Mathematical Sciences
    67 rdf:type schema:DefinedTerm
    68 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Pure Mathematics
    70 rdf:type schema:DefinedTerm
    71 sg:person.010020724604.82 schema:affiliation https://www.grid.ac/institutes/grid.57926.3f
    72 schema:familyName Yang
    73 schema:givenName Boting
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010020724604.82
    75 rdf:type schema:Person
    76 sg:person.012155470203.67 schema:affiliation https://www.grid.ac/institutes/grid.57926.3f
    77 schema:familyName Alspach
    78 schema:givenName Brian
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012155470203.67
    80 rdf:type schema:Person
    81 sg:person.015173770711.52 schema:affiliation https://www.grid.ac/institutes/grid.61971.38
    82 schema:familyName Dyer
    83 schema:givenName Danny
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015173770711.52
    85 rdf:type schema:Person
    86 sg:pub.10.1007/978-3-540-39890-5_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025064061
    87 https://doi.org/10.1007/978-3-540-39890-5_4
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1016/0196-6774(91)90003-h schema:sameAs https://app.dimensions.ai/details/publication/pub.1033945460
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1145/151261.151263 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017456454
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1145/42267.42268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045068727
    94 rdf:type schema:CreativeWork
    95 https://www.grid.ac/institutes/grid.57926.3f schema:alternateName University of Regina
    96 schema:name Department of Computer Science, University of Regina
    97 Department of Mathematics and Statistics, University of Regina
    98 rdf:type schema:Organization
    99 https://www.grid.ac/institutes/grid.61971.38 schema:alternateName Simon Fraser University
    100 schema:name Department of Mathematics, Simon Fraser University
    101 rdf:type schema:Organization
     




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


    ...