Connected Treewidth and Connected Graph Searching View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Pierre Fraigniaud , Nicolas Nisse

ABSTRACT

We give a constructive proof of the equality between treewidth and connected treewidth. More precisely, we describe an O(nk3)-time algorithm that, given any n-node width-k tree-decomposition of a connected graph G, returns a connected tree-decomposition of G of width ≤ k. The equality between treewidth and connected treewidth finds applications in graph searching problems. First, using equality between treewidth and connected treewidth, we prove that the connected search number cs(G) of a connected graph G is at most logn+1 times larger than its search number. Second, using our constructive proof of equality between treewidth and connected treewidth, we design an )-approximation algorithm for connected search, running in time O(t(n)+nk3log3/2k+mlog n) for n-node m-edge connected graphs of treewidth at most k, where t(n) is the time-complexity of the fastest algorithm for approximating the treewidth, up to a factor ). More... »

PAGES

479-490

References to SciGraph publications

  • 2003. Searching Is Not Jumping in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 2004. Sweeping Graphs with Large Clique Number in ALGORITHMS AND COMPUTATION
  • 1994-06. Call routing and the ratcatcher in COMBINATORICA
  • Book

    TITLE

    LATIN 2006: Theoretical Informatics

    ISBN

    978-3-540-32755-4
    978-3-540-32756-1

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11682462_45

    DOI

    http://dx.doi.org/10.1007/11682462_45

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "name": [
                "CNRS, Lab. de Recherche en Informatique, Universit\u00e9 Paris-Sud, 91405, Orsay, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fraigniaud", 
            "givenName": "Pierre", 
            "id": "sg:person.013424402135.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Paris-Sud", 
              "id": "https://www.grid.ac/institutes/grid.5842.b", 
              "name": [
                "Lab. de Recherche en Informatique, Universit\u00e9 Paris-Sud, 91405, Orsay, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nisse", 
            "givenName": "Nicolas", 
            "id": "sg:person.011706712653.72", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011706712653.72"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-30551-4_77", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020618149", 
              "https://doi.org/10.1007/978-3-540-30551-4_77"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30551-4_77", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020618149", 
              "https://doi.org/10.1007/978-3-540-30551-4_77"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(86)90023-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021500239"
            ], 
            "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.1006/inco.1994.1064", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037418865"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0166-218x(97)00041-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039312172"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/42267.42268", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045068727"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0095-8956(91)90061-n", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047643417"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01215352", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048905282", 
              "https://doi.org/10.1007/bf01215352"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01215352", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048905282", 
              "https://doi.org/10.1007/bf01215352"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/564870.564906", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051619886"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1060590.1060674", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051843791"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/dimacs/005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1097022547"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2006", 
        "datePublishedReg": "2006-01-01", 
        "description": "We give a constructive proof of the equality between treewidth and connected treewidth. More precisely, we describe an O(nk3)-time algorithm that, given any n-node width-k tree-decomposition of a connected graph G, returns a connected tree-decomposition of G of width \u2264 k. The equality between treewidth and connected treewidth finds applications in graph searching problems. First, using equality between treewidth and connected treewidth, we prove that the connected search number cs(G) of a connected graph G is at most logn+1 times larger than its search number. Second, using our constructive proof of equality between treewidth and connected treewidth, we design an )-approximation algorithm for connected search, running in time O(t(n)+nk3log3/2k+mlog n) for n-node m-edge connected graphs of treewidth at most k, where t(n) is the time-complexity of the fastest algorithm for approximating the treewidth, up to a factor ).", 
        "editor": [
          {
            "familyName": "Correa", 
            "givenName": "Jos\u00e9 R.", 
            "type": "Person"
          }, 
          {
            "familyName": "Hevia", 
            "givenName": "Alejandro", 
            "type": "Person"
          }, 
          {
            "familyName": "Kiwi", 
            "givenName": "Marcos", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11682462_45", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-32755-4", 
            "978-3-540-32756-1"
          ], 
          "name": "LATIN 2006: Theoretical Informatics", 
          "type": "Book"
        }, 
        "name": "Connected Treewidth and Connected Graph Searching", 
        "pagination": "479-490", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1022989737"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11682462_45"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "6d87499c740fd56838cbf9598e5e24517045b9ffc6a36af7949f56c9d1bf14cb"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11682462_45", 
          "https://app.dimensions.ai/details/publication/pub.1022989737"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:31", 
        "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/0000000356_0000000356/records_57889_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11682462_45"
      }
    ]
     

    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/11682462_45'

    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/11682462_45'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11682462_45'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11682462_45'


     

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

    123 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11682462_45 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N1f935f30b52b45b4b8552d587e45f4ab
    4 schema:citation sg:pub.10.1007/978-3-540-30551-4_77
    5 sg:pub.10.1007/978-3-540-39890-5_4
    6 sg:pub.10.1007/bf01215352
    7 https://doi.org/10.1006/inco.1994.1064
    8 https://doi.org/10.1016/0095-8956(91)90061-n
    9 https://doi.org/10.1016/0196-6774(86)90023-4
    10 https://doi.org/10.1016/0196-6774(91)90003-h
    11 https://doi.org/10.1016/s0166-218x(97)00041-3
    12 https://doi.org/10.1090/dimacs/005
    13 https://doi.org/10.1145/1060590.1060674
    14 https://doi.org/10.1145/42267.42268
    15 https://doi.org/10.1145/564870.564906
    16 schema:datePublished 2006
    17 schema:datePublishedReg 2006-01-01
    18 schema:description We give a constructive proof of the equality between treewidth and connected treewidth. More precisely, we describe an O(nk3)-time algorithm that, given any n-node width-k tree-decomposition of a connected graph G, returns a connected tree-decomposition of G of width ≤ k. The equality between treewidth and connected treewidth finds applications in graph searching problems. First, using equality between treewidth and connected treewidth, we prove that the connected search number cs(G) of a connected graph G is at most logn+1 times larger than its search number. Second, using our constructive proof of equality between treewidth and connected treewidth, we design an )-approximation algorithm for connected search, running in time O(t(n)+nk3log3/2k+mlog n) for n-node m-edge connected graphs of treewidth at most k, where t(n) is the time-complexity of the fastest algorithm for approximating the treewidth, up to a factor ).
    19 schema:editor N1043df74f73940a1bc84d4760bd7f1ce
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree false
    23 schema:isPartOf N632fcbc1f3f94a8b9992346b6556789b
    24 schema:name Connected Treewidth and Connected Graph Searching
    25 schema:pagination 479-490
    26 schema:productId N4ed91523398740be850ce2d9513db45d
    27 Nb8d6378bbe534c37b5eb49174481f661
    28 Nc6f86fcbec744103a6a0ad1e65b7ab4f
    29 schema:publisher N24bf4f1aebf3462c9e8ae49d9073336e
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022989737
    31 https://doi.org/10.1007/11682462_45
    32 schema:sdDatePublished 2019-04-16T07:31
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N51c8050107db40059267bd4f84b0c149
    35 schema:url https://link.springer.com/10.1007%2F11682462_45
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N0258e408a40c4d20afea4b0e38b89a38 rdf:first Ne6a5253afc1e4c4299e67b556ea1396a
    40 rdf:rest rdf:nil
    41 N1043df74f73940a1bc84d4760bd7f1ce rdf:first N8a32677a278e4545aaad296a9d9116e2
    42 rdf:rest N3d71c1d55eb0403c9321c8426d4247cb
    43 N1f935f30b52b45b4b8552d587e45f4ab rdf:first sg:person.013424402135.28
    44 rdf:rest Nfb6649e3110c4915b4ab80a8437b0d4e
    45 N24bf4f1aebf3462c9e8ae49d9073336e schema:location Berlin, Heidelberg
    46 schema:name Springer Berlin Heidelberg
    47 rdf:type schema:Organisation
    48 N3d71c1d55eb0403c9321c8426d4247cb rdf:first Ndcf1ea5181ea44b4927cf8e3b85fcfd7
    49 rdf:rest N0258e408a40c4d20afea4b0e38b89a38
    50 N4ed91523398740be850ce2d9513db45d schema:name readcube_id
    51 schema:value 6d87499c740fd56838cbf9598e5e24517045b9ffc6a36af7949f56c9d1bf14cb
    52 rdf:type schema:PropertyValue
    53 N51c8050107db40059267bd4f84b0c149 schema:name Springer Nature - SN SciGraph project
    54 rdf:type schema:Organization
    55 N632fcbc1f3f94a8b9992346b6556789b schema:isbn 978-3-540-32755-4
    56 978-3-540-32756-1
    57 schema:name LATIN 2006: Theoretical Informatics
    58 rdf:type schema:Book
    59 N7bc7218601de4dda8aa48ad71ea69cc2 schema:name CNRS, Lab. de Recherche en Informatique, Université Paris-Sud, 91405, Orsay, France
    60 rdf:type schema:Organization
    61 N8a32677a278e4545aaad296a9d9116e2 schema:familyName Correa
    62 schema:givenName José R.
    63 rdf:type schema:Person
    64 Nb8d6378bbe534c37b5eb49174481f661 schema:name dimensions_id
    65 schema:value pub.1022989737
    66 rdf:type schema:PropertyValue
    67 Nc6f86fcbec744103a6a0ad1e65b7ab4f schema:name doi
    68 schema:value 10.1007/11682462_45
    69 rdf:type schema:PropertyValue
    70 Ndcf1ea5181ea44b4927cf8e3b85fcfd7 schema:familyName Hevia
    71 schema:givenName Alejandro
    72 rdf:type schema:Person
    73 Ne6a5253afc1e4c4299e67b556ea1396a schema:familyName Kiwi
    74 schema:givenName Marcos
    75 rdf:type schema:Person
    76 Nfb6649e3110c4915b4ab80a8437b0d4e rdf:first sg:person.011706712653.72
    77 rdf:rest rdf:nil
    78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Information and Computing Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Computation Theory and Mathematics
    83 rdf:type schema:DefinedTerm
    84 sg:person.011706712653.72 schema:affiliation https://www.grid.ac/institutes/grid.5842.b
    85 schema:familyName Nisse
    86 schema:givenName Nicolas
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011706712653.72
    88 rdf:type schema:Person
    89 sg:person.013424402135.28 schema:affiliation N7bc7218601de4dda8aa48ad71ea69cc2
    90 schema:familyName Fraigniaud
    91 schema:givenName Pierre
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28
    93 rdf:type schema:Person
    94 sg:pub.10.1007/978-3-540-30551-4_77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020618149
    95 https://doi.org/10.1007/978-3-540-30551-4_77
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/978-3-540-39890-5_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025064061
    98 https://doi.org/10.1007/978-3-540-39890-5_4
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/bf01215352 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048905282
    101 https://doi.org/10.1007/bf01215352
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1006/inco.1994.1064 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037418865
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/0095-8956(91)90061-n schema:sameAs https://app.dimensions.ai/details/publication/pub.1047643417
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/0196-6774(86)90023-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021500239
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/0196-6774(91)90003-h schema:sameAs https://app.dimensions.ai/details/publication/pub.1033945460
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1016/s0166-218x(97)00041-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039312172
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1090/dimacs/005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1097022547
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1145/1060590.1060674 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051843791
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1145/42267.42268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045068727
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1145/564870.564906 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051619886
    120 rdf:type schema:CreativeWork
    121 https://www.grid.ac/institutes/grid.5842.b schema:alternateName University of Paris-Sud
    122 schema:name Lab. de Recherche en Informatique, Université Paris-Sud, 91405, Orsay, France
    123 rdf:type schema:Organization
     




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


    ...