File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: NP-completeness results for all-shortest-path interval routing

TitleNP-completeness results for all-shortest-path interval routing
Authors
KeywordsCompact Routing
Interval Routing
Np-Completeness
Issue Date2004
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3104, p. 267-278 How to Cite?
Abstractk-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. Many of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problem remains open for k ≥ 1. We investigate the time complexity of devising minimal-space all-shortest-path k-IRS and prove that it is NP-complete to decide whether a graph admits an all-shortest-path k-IRS, for every integer k ≥ 3, as well as whether a graph admits an all-shortest-path k-strict IRS, for every integer k ≥ 4. These are the first NP-completeness results for all-shortest-path k-IRS where k is a constant and the graph is unweighted. Moreover, the NP-completeness holds also for the linear case. © Springer-Verlag Berlin Heidelberg 2004.
Persistent Identifierhttp://hdl.handle.net/10722/152369
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorWang, Ren_US
dc.contributor.authorLau, FCMen_US
dc.contributor.authorLiu, YYen_US
dc.date.accessioned2012-06-26T06:37:40Z-
dc.date.available2012-06-26T06:37:40Z-
dc.date.issued2004en_US
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3104, p. 267-278en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/152369-
dc.description.abstractk-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. Many of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problem remains open for k ≥ 1. We investigate the time complexity of devising minimal-space all-shortest-path k-IRS and prove that it is NP-complete to decide whether a graph admits an all-shortest-path k-IRS, for every integer k ≥ 3, as well as whether a graph admits an all-shortest-path k-strict IRS, for every integer k ≥ 4. These are the first NP-completeness results for all-shortest-path k-IRS where k is a constant and the graph is unweighted. Moreover, the NP-completeness holds also for the linear case. © Springer-Verlag Berlin Heidelberg 2004.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.subjectCompact Routingen_US
dc.subjectInterval Routingen_US
dc.subjectNp-Completenessen_US
dc.titleNP-completeness results for all-shortest-path interval routingen_US
dc.typeArticleen_US
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_US
dc.identifier.authorityLau, FCM=rp00221en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-35048880180en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35048880180&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume3104en_US
dc.identifier.spage267en_US
dc.identifier.epage278en_US
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridWang, R=36072127500en_US
dc.identifier.scopusauthoridLau, FCM=7102749723en_US
dc.identifier.scopusauthoridLiu, YY=35248480000en_US
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats