NP-Completeness of st-Orientations for Plane Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Sadish Sadasivam , Huaming Zhang

ABSTRACT

An st-orientation or bipolar orientation of a 2-connected graph G is an orientation of its edges to generate a directed acyclic graph with a single source s and a single sink t. Given a plane graph G and two vertices s and t on the exterior face of G, the problem of finding an optimum st-orientation, i.e., an st-orientation in which the length of the longest st-path is minimized, was first proposed indirectly by Rosenstiehl and Tarjan in [14] and then later directly by He and Kao in [6]. In this paper, we prove that, given a 2-connected plane graph G, two vertices s, t, on the exterior face of G and a positive integer K, the decision problem of whether G has an st-orientation, where the maximum length of an st-path is ≤ K, is NP-Complete. This solves a long standing open problem on the complexity of optimum st-orientations for plane graphs. More... »

PAGES

298-309

Book

TITLE

Fundamentals of Computation Theory

ISBN

978-3-642-03408-4
978-3-642-03409-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03409-1_27

DOI

http://dx.doi.org/10.1007/978-3-642-03409-1_27

DIMENSIONS

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


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": "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA", 
          "id": "http://www.grid.ac/institutes/grid.265893.3", 
          "name": [
            "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sadasivam", 
        "givenName": "Sadish", 
        "id": "sg:person.015341066775.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015341066775.96"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA", 
          "id": "http://www.grid.ac/institutes/grid.265893.3", 
          "name": [
            "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Huaming", 
        "id": "sg:person.012041227127.88", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "An st-orientation or bipolar orientation of a 2-connected graph G is an orientation of its edges to generate a directed acyclic graph with a single source s and a single sink t. Given a plane graph G and two vertices s and t on the exterior face of G, the problem of finding an optimum st-orientation, i.e., an st-orientation in which the length of the longest st-path is minimized, was first proposed indirectly by Rosenstiehl and Tarjan in [14] and then later directly by He and Kao in [6]. In this paper, we prove that, given a 2-connected plane graph G, two vertices s, t, on the exterior face of G and a positive integer K, the decision problem of whether G has an st-orientation, where the maximum length of an st-path is \u2264\u2009K, is NP-Complete. This solves a long standing open problem on the complexity of optimum st-orientations for plane graphs.", 
    "editor": [
      {
        "familyName": "Kuty\u0142owski", 
        "givenName": "Miros\u0142aw", 
        "type": "Person"
      }, 
      {
        "familyName": "Charatonik", 
        "givenName": "Witold", 
        "type": "Person"
      }, 
      {
        "familyName": "G\u0119bala", 
        "givenName": "Maciej", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03409-1_27", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03408-4", 
        "978-3-642-03409-1"
      ], 
      "name": "Fundamentals of Computation Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "graph G", 
      "plane graph G", 
      "vertices s", 
      "plane graph", 
      "bipolar orientation", 
      "orientation", 
      "edge", 
      "acyclic graph", 
      "graph", 
      "single source s", 
      "source s", 
      "sink t.", 
      "T.", 
      "exterior face", 
      "face", 
      "problem", 
      "length", 
      "st-paths", 
      "Rosenstiehl", 
      "Tarjan", 
      "Kao", 
      "positive integer k", 
      "integer k", 
      "decision problem", 
      "maximum length", 
      "NPs", 
      "open problem", 
      "complexity", 
      "st-orientations", 
      "NP-completeness", 
      "paper"
    ], 
    "name": "NP-Completeness of st-Orientations for Plane Graphs", 
    "pagination": "298-309", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050455240"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03409-1_27"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03409-1_27", 
      "https://app.dimensions.ai/details/publication/pub.1050455240"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:43", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_22.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-03409-1_27"
  }
]
 

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-03409-1_27'

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-03409-1_27'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03409-1_27'

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-03409-1_27'


 

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

108 TRIPLES      23 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03409-1_27 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ncf33555b612f41b7885c0134d4dd09fd
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description An st-orientation or bipolar orientation of a 2-connected graph G is an orientation of its edges to generate a directed acyclic graph with a single source s and a single sink t. Given a plane graph G and two vertices s and t on the exterior face of G, the problem of finding an optimum st-orientation, i.e., an st-orientation in which the length of the longest st-path is minimized, was first proposed indirectly by Rosenstiehl and Tarjan in [14] and then later directly by He and Kao in [6]. In this paper, we prove that, given a 2-connected plane graph G, two vertices s, t, on the exterior face of G and a positive integer K, the decision problem of whether G has an st-orientation, where the maximum length of an st-path is ≤ K, is NP-Complete. This solves a long standing open problem on the complexity of optimum st-orientations for plane graphs.
7 schema:editor Nf54424dd77a84581b8e6c8815f159d72
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N64fa80f454884298b0cec052f0784d7b
12 schema:keywords Kao
13 NP-completeness
14 NPs
15 Rosenstiehl
16 T.
17 Tarjan
18 acyclic graph
19 bipolar orientation
20 complexity
21 decision problem
22 edge
23 exterior face
24 face
25 graph
26 graph G
27 integer k
28 length
29 maximum length
30 open problem
31 orientation
32 paper
33 plane graph
34 plane graph G
35 positive integer k
36 problem
37 single source s
38 sink t.
39 source s
40 st-orientations
41 st-paths
42 vertices s
43 schema:name NP-Completeness of st-Orientations for Plane Graphs
44 schema:pagination 298-309
45 schema:productId N1e51ff56ff8d4314af6d866b6ef6f87c
46 N3167d6981bc3466b99f25d507fa0cf7b
47 schema:publisher N8579088470e34199a0982e553452fb39
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050455240
49 https://doi.org/10.1007/978-3-642-03409-1_27
50 schema:sdDatePublished 2022-05-20T07:43
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher N0428f04915eb4b04a78b983785b804dc
53 schema:url https://doi.org/10.1007/978-3-642-03409-1_27
54 sgo:license sg:explorer/license/
55 sgo:sdDataset chapters
56 rdf:type schema:Chapter
57 N0428f04915eb4b04a78b983785b804dc schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N0ad4fd0a35d44300ae69c514224979f2 schema:familyName Gębala
60 schema:givenName Maciej
61 rdf:type schema:Person
62 N17046a25f7734086a3f5e01a048120b1 schema:familyName Charatonik
63 schema:givenName Witold
64 rdf:type schema:Person
65 N1e51ff56ff8d4314af6d866b6ef6f87c schema:name doi
66 schema:value 10.1007/978-3-642-03409-1_27
67 rdf:type schema:PropertyValue
68 N2a83c14a0b9d49ed9d5faec549e14a6e rdf:first sg:person.012041227127.88
69 rdf:rest rdf:nil
70 N2fcf3cbed40e43fa80b9099bdb0eded2 rdf:first N17046a25f7734086a3f5e01a048120b1
71 rdf:rest Na419ea6130af43eb8f997a1e327a01e6
72 N3167d6981bc3466b99f25d507fa0cf7b schema:name dimensions_id
73 schema:value pub.1050455240
74 rdf:type schema:PropertyValue
75 N42313ab2b73a449293dae5be768807e5 schema:familyName Kutyłowski
76 schema:givenName Mirosław
77 rdf:type schema:Person
78 N64fa80f454884298b0cec052f0784d7b schema:isbn 978-3-642-03408-4
79 978-3-642-03409-1
80 schema:name Fundamentals of Computation Theory
81 rdf:type schema:Book
82 N8579088470e34199a0982e553452fb39 schema:name Springer Nature
83 rdf:type schema:Organisation
84 Na419ea6130af43eb8f997a1e327a01e6 rdf:first N0ad4fd0a35d44300ae69c514224979f2
85 rdf:rest rdf:nil
86 Ncf33555b612f41b7885c0134d4dd09fd rdf:first sg:person.015341066775.96
87 rdf:rest N2a83c14a0b9d49ed9d5faec549e14a6e
88 Nf54424dd77a84581b8e6c8815f159d72 rdf:first N42313ab2b73a449293dae5be768807e5
89 rdf:rest N2fcf3cbed40e43fa80b9099bdb0eded2
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
94 schema:name Computation Theory and Mathematics
95 rdf:type schema:DefinedTerm
96 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
97 schema:familyName Zhang
98 schema:givenName Huaming
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
100 rdf:type schema:Person
101 sg:person.015341066775.96 schema:affiliation grid-institutes:grid.265893.3
102 schema:familyName Sadasivam
103 schema:givenName Sadish
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015341066775.96
105 rdf:type schema:Person
106 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
107 schema:name Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
108 rdf:type schema:Organization
 




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


...