File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On the hardness of minimizing space for all-shortest-path interval routing schemes

TitleOn the hardness of minimizing space for all-shortest-path interval routing schemes
Authors
KeywordsCompact routing
Interval routing schemes
NP-completeness
Issue Date2007
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2007, v. 389 n. 1-2, p. 250-264 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; and global k-IRS allows not more than a total of k interval labels in the whole network. A fundamental problem is to characterize the networks that admit k-IRS (or global 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. In this paper, we study the time complexity of devising minimal-space all-shortest-path k-IRSs and show that it is NP-complete to decide whether a graph admits an all-shortest-path k-IRS, for every integer k ≥ 3, and so is that of deciding 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. The NP-completeness holds also for the linear case. We also prove that it is NP-complete to decide whether an unweighted graph admits an all-shortest-path IRS with global compactness of at most k, which also holds for the linear and strict cases. © 2007 Elsevier Ltd. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/89075
ISSN
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorWang, Ren_HK
dc.contributor.authorLau, FCMen_HK
dc.contributor.authorLiu, YYen_HK
dc.date.accessioned2010-09-06T09:52:04Z-
dc.date.available2010-09-06T09:52:04Z-
dc.date.issued2007en_HK
dc.identifier.citationTheoretical Computer Science, 2007, v. 389 n. 1-2, p. 250-264en_HK
dc.identifier.issn0304-3975en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89075-
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; and global k-IRS allows not more than a total of k interval labels in the whole network. A fundamental problem is to characterize the networks that admit k-IRS (or global 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. In this paper, we study the time complexity of devising minimal-space all-shortest-path k-IRSs and show that it is NP-complete to decide whether a graph admits an all-shortest-path k-IRS, for every integer k ≥ 3, and so is that of deciding 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. The NP-completeness holds also for the linear case. We also prove that it is NP-complete to decide whether an unweighted graph admits an all-shortest-path IRS with global compactness of at most k, which also holds for the linear and strict cases. © 2007 Elsevier Ltd. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_HK
dc.relation.ispartofTheoretical Computer Scienceen_HK
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.subjectCompact routingen_HK
dc.subjectInterval routing schemesen_HK
dc.subjectNP-completenessen_HK
dc.titleOn the hardness of minimizing space for all-shortest-path interval routing schemesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=389&spage=250&epage=264&date=2007&atitle=On+The+Hardness+Of+Minimizing+Space+For+All-shortest-path+Interval+Routing+Schemesen_HK
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_HK
dc.identifier.authorityLau, FCM=rp00221en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.tcs.2007.09.010en_HK
dc.identifier.scopuseid_2-s2.0-36049033660en_HK
dc.identifier.hkuros138818en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-36049033660&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume389en_HK
dc.identifier.issue1-2en_HK
dc.identifier.spage250en_HK
dc.identifier.epage264en_HK
dc.identifier.isiWOS:000251695800021-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridWang, R=25653261600en_HK
dc.identifier.scopusauthoridLau, FCM=7102749723en_HK
dc.identifier.scopusauthoridLiu, YY=35248480000en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats