| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font
First page > Show document

Show document Help

Title:Strong edge geodetic problem in networks
Authors:ID Manuel, Paul (Author)
ID Klavžar, Sandi (Author)
ID Xavier, Antony (Author)
ID Arokiaraj, Andrew (Author)
ID Thomas, Elizabeth (Author)
Files:.pdf Open_Mathematics_2017_Manuel_et_al._Strong_edge_geodetic_problem_in_networks.pdf (657,86 KB)
MD5: BFB598C40E4C2D53DB19480118EC7830
PID: 20.500.12556/dkum/03439a33-ee05-49d6-b841-054e77141093
 
URL http://www.degruyter.com/view/j/math.2017.15.issue-1/math-2017-0101/math-2017-0101.xml
 
Language:English
Work type:Scientific work
Typology:1.01 - Original Scientific Article
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract:Geodesic covering problems form a widely researched topic in graph theory. One such problem is geodetic problem introduced by Harary et al. Here we introduce a variation of the geodetic problem and call it strong edge geodetic problem. We illustrate how this problem is evolved from social transport networks. It is shown that the strong edge geodetic problem is NP-complete. We derive lower and upper bounds for the strong edge geodetic number and demonstrate that these bounds are sharp. We produce exact solutions for trees, block graphs, silicate networks and glued binary trees without randomization.
Keywords:geodetic problem, strong edge geodetic problem, computational complexity, transport networks
Publication status:Published
Publication version:Version of Record
Year of publishing:2017
Number of pages:str. 1225-1235
Numbering:Letn. 15, št. 1
PID:20.500.12556/DKUM-68859 New window
ISSN:Y508-704X
UDC:519.17
ISSN on article:Y508-704X
COBISS.SI-ID:18142553 New window
DOI:10.1515/math-2017-0101 New window
NUK URN:URN:SI:UM:DK:W5ZNBWRO
Publication date in DKUM:03.11.2017
Views:1194
Downloads:450
Metadata:XML DC-XML DC-RDF
Categories:Misc.
:
MANUEL, Paul, KLAVŽAR, Sandi, XAVIER, Antony, AROKIARAJ, Andrew and THOMAS, Elizabeth, 2017, Strong edge geodetic problem in networks. Open Mathematics [online]. 2017. Vol. 15, no. 1, p. 1225–1235. [Accessed 13 April 2025]. DOI 10.1515/math-2017-0101. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=68859
Copy citation
  
Average score:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Open Mathematics
Shortened title:Open Math.
Publisher:De Gruyter Open
ISSN:2391-5455
COBISS.SI-ID:17824345 New window

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:03.11.2017

Secondary language

Language:Slovenian
Title:Krepki povezavno-geodetski problem v omrežjih
Abstract:Problemi geodetskih pokrivanj tvorijo obsežno raziskovalno področje v teoriji grafov. Eden izmed njih je geodetski problem, ki so ga vpeljali Harary in drugi. V tem članku vpeljemo inačico geodetskega problema, ki jo poimenujemo krepki povezavno-geodetski problem. Opišemo, kako je bil ta problem porojen iz socialnih transportnih omrežij. Dokažemo, da je krepki povezavno-geodetski problem NP-poln. Izpeljemo spodnje in zgornje meje za krepko povezavno-geodetsko število in pokažemo, da so meje tesne. Dokažemo tudi točne vrednosti za drevesa, bločne grafe, silikatna omrežja in zlepljena binarna drevesa brez slučajnosti.
Keywords:geodetski problem, krepki povezavno-geodetski problem, računska zahtevnost, transportno omrežje


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica