Construction Techniques for Digraphs with Minimum Diameter View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Mirka Miller , Slamin , Joe Ryan , Edy Tri Baskoro

ABSTRACT

We consider the so-called order/degree problem, that is, to determine the smallest diameter of a digraph given order and maximum out-degree. There is no general efficient algorithm known for the construction of such optimal digraphs but various construction techniques for digraphs with minimum diameter have been proposed. In this paper, we survey the known techniques. More... »

PAGES

327-336

References to SciGraph publications

Book

TITLE

Combinatorial Algorithms

ISBN

978-3-642-45277-2
978-3-642-45278-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-45278-9_28

DOI

http://dx.doi.org/10.1007/978-3-642-45278-9_28

DIMENSIONS

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


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/0905", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Civil Engineering", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/09", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Engineering", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Newcastle Australia", 
          "id": "https://www.grid.ac/institutes/grid.266842.c", 
          "name": [
            "School of Mathematical and Physical Sciences, University of Newcastle, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Miller", 
        "givenName": "Mirka", 
        "id": "sg:person.07654672465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07654672465.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Universitas Jember", 
          "id": "https://www.grid.ac/institutes/grid.443500.6", 
          "name": [
            "School of Information Systems, University of Jember, Indonesia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Slamin", 
        "id": "sg:person.013236557261.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013236557261.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Newcastle Australia", 
          "id": "https://www.grid.ac/institutes/grid.266842.c", 
          "name": [
            "School of Electrical Engineering and Computer Science, University of Newcastle, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ryan", 
        "givenName": "Joe", 
        "id": "sg:person.014235535465.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014235535465.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Mathematics, ITB Bandung, Indonesia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Baskoro", 
        "givenName": "Edy Tri", 
        "id": "sg:person.013050576574.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013050576574.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1093/comjnl/31.1.71", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004450949"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0095-8956(80)90091-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012691415"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-44968-x_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042681390", 
          "https://doi.org/10.1007/3-540-44968-x_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-44968-x_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042681390", 
          "https://doi.org/10.1007/3-540-44968-x_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/12.256453", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061087777"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tc.1981.1675809", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061532577"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tc.1983.1676323", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061532974"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tc.1984.1676455", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061533071"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We consider the so-called order/degree problem, that is, to determine the smallest diameter of a digraph given order and maximum out-degree. There is no general efficient algorithm known for the construction of such optimal digraphs but various construction techniques for digraphs with minimum diameter have been proposed. In this paper, we survey the known techniques.", 
    "editor": [
      {
        "familyName": "Lecroq", 
        "givenName": "Thierry", 
        "type": "Person"
      }, 
      {
        "familyName": "Mouchard", 
        "givenName": "Laurent", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-45278-9_28", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-45277-2", 
        "978-3-642-45278-9"
      ], 
      "name": "Combinatorial Algorithms", 
      "type": "Book"
    }, 
    "name": "Construction Techniques for Digraphs with Minimum Diameter", 
    "pagination": "327-336", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-45278-9_28"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "9352b1aec2e35430f6b1206275f471b39b882040c845c12327b2097afe4772e6"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030924840"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-45278-9_28", 
      "https://app.dimensions.ai/details/publication/pub.1030924840"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T21:59", 
    "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/0000000001_0000000264/records_8693_00000262.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-45278-9_28"
  }
]
 

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-45278-9_28'

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-45278-9_28'

Turtle is a human-readable linked data format.

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

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-45278-9_28'


 

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

118 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-45278-9_28 schema:about anzsrc-for:09
2 anzsrc-for:0905
3 schema:author Nf85320d35b924b17a8250169239b9720
4 schema:citation sg:pub.10.1007/3-540-44968-x_19
5 https://doi.org/10.1016/0095-8956(80)90091-x
6 https://doi.org/10.1093/comjnl/31.1.71
7 https://doi.org/10.1109/12.256453
8 https://doi.org/10.1109/tc.1981.1675809
9 https://doi.org/10.1109/tc.1983.1676323
10 https://doi.org/10.1109/tc.1984.1676455
11 schema:datePublished 2013
12 schema:datePublishedReg 2013-01-01
13 schema:description We consider the so-called order/degree problem, that is, to determine the smallest diameter of a digraph given order and maximum out-degree. There is no general efficient algorithm known for the construction of such optimal digraphs but various construction techniques for digraphs with minimum diameter have been proposed. In this paper, we survey the known techniques.
14 schema:editor N48a53b247d034074872220b000100119
15 schema:genre chapter
16 schema:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf Naeef0077f5404f07b8c3f800ba2f3593
19 schema:name Construction Techniques for Digraphs with Minimum Diameter
20 schema:pagination 327-336
21 schema:productId N4412d9d296bb44b286d1aa03f01aa7a5
22 N84f1c502540a4a94b216d78ee9fea76c
23 Nb0e8edf01ffa474d90df2f9053048cbc
24 schema:publisher Nd0d6d2ffb0594f0aa8c3f187bfefb74c
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030924840
26 https://doi.org/10.1007/978-3-642-45278-9_28
27 schema:sdDatePublished 2019-04-15T21:59
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher N349119f3bc144444b86f0d44735548b5
30 schema:url http://link.springer.com/10.1007/978-3-642-45278-9_28
31 sgo:license sg:explorer/license/
32 sgo:sdDataset chapters
33 rdf:type schema:Chapter
34 N21aee93953b04afd9830ed3c06abf6f6 schema:familyName Lecroq
35 schema:givenName Thierry
36 rdf:type schema:Person
37 N2833d096997f408a98e90d18df0e0769 rdf:first sg:person.013236557261.83
38 rdf:rest Nd0f905d7749b4c09b6a370a41f44977b
39 N349119f3bc144444b86f0d44735548b5 schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N4412d9d296bb44b286d1aa03f01aa7a5 schema:name dimensions_id
42 schema:value pub.1030924840
43 rdf:type schema:PropertyValue
44 N48a53b247d034074872220b000100119 rdf:first N21aee93953b04afd9830ed3c06abf6f6
45 rdf:rest Na2bdebb4a38f4aa892b713cbd8584a90
46 N54d544e0dc27426c97efe64bc8739b03 schema:familyName Mouchard
47 schema:givenName Laurent
48 rdf:type schema:Person
49 N84f1c502540a4a94b216d78ee9fea76c schema:name readcube_id
50 schema:value 9352b1aec2e35430f6b1206275f471b39b882040c845c12327b2097afe4772e6
51 rdf:type schema:PropertyValue
52 Na2bdebb4a38f4aa892b713cbd8584a90 rdf:first N54d544e0dc27426c97efe64bc8739b03
53 rdf:rest rdf:nil
54 Naeef0077f5404f07b8c3f800ba2f3593 schema:isbn 978-3-642-45277-2
55 978-3-642-45278-9
56 schema:name Combinatorial Algorithms
57 rdf:type schema:Book
58 Nb0179104f59145229f132cd2f297becb rdf:first sg:person.013050576574.28
59 rdf:rest rdf:nil
60 Nb0e8edf01ffa474d90df2f9053048cbc schema:name doi
61 schema:value 10.1007/978-3-642-45278-9_28
62 rdf:type schema:PropertyValue
63 Nd0d6d2ffb0594f0aa8c3f187bfefb74c schema:location Berlin, Heidelberg
64 schema:name Springer Berlin Heidelberg
65 rdf:type schema:Organisation
66 Nd0f905d7749b4c09b6a370a41f44977b rdf:first sg:person.014235535465.60
67 rdf:rest Nb0179104f59145229f132cd2f297becb
68 Nebd83f638faa4995aee4346b58e6d222 schema:name Department of Mathematics, ITB Bandung, Indonesia
69 rdf:type schema:Organization
70 Nf85320d35b924b17a8250169239b9720 rdf:first sg:person.07654672465.63
71 rdf:rest N2833d096997f408a98e90d18df0e0769
72 anzsrc-for:09 schema:inDefinedTermSet anzsrc-for:
73 schema:name Engineering
74 rdf:type schema:DefinedTerm
75 anzsrc-for:0905 schema:inDefinedTermSet anzsrc-for:
76 schema:name Civil Engineering
77 rdf:type schema:DefinedTerm
78 sg:person.013050576574.28 schema:affiliation Nebd83f638faa4995aee4346b58e6d222
79 schema:familyName Baskoro
80 schema:givenName Edy Tri
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013050576574.28
82 rdf:type schema:Person
83 sg:person.013236557261.83 schema:affiliation https://www.grid.ac/institutes/grid.443500.6
84 schema:familyName Slamin
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013236557261.83
86 rdf:type schema:Person
87 sg:person.014235535465.60 schema:affiliation https://www.grid.ac/institutes/grid.266842.c
88 schema:familyName Ryan
89 schema:givenName Joe
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014235535465.60
91 rdf:type schema:Person
92 sg:person.07654672465.63 schema:affiliation https://www.grid.ac/institutes/grid.266842.c
93 schema:familyName Miller
94 schema:givenName Mirka
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07654672465.63
96 rdf:type schema:Person
97 sg:pub.10.1007/3-540-44968-x_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042681390
98 https://doi.org/10.1007/3-540-44968-x_19
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/0095-8956(80)90091-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1012691415
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1093/comjnl/31.1.71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004450949
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1109/12.256453 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061087777
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1109/tc.1981.1675809 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532577
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1109/tc.1983.1676323 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532974
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1109/tc.1984.1676455 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533071
111 rdf:type schema:CreativeWork
112 https://www.grid.ac/institutes/grid.266842.c schema:alternateName University of Newcastle Australia
113 schema:name School of Electrical Engineering and Computer Science, University of Newcastle, Australia
114 School of Mathematical and Physical Sciences, University of Newcastle, Australia
115 rdf:type schema:Organization
116 https://www.grid.ac/institutes/grid.443500.6 schema:alternateName Universitas Jember
117 schema:name School of Information Systems, University of Jember, Indonesia
118 rdf:type schema:Organization
 




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


...