File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.tcs.2007.09.010
- Scopus: eid_2-s2.0-36049033660
- WOS: WOS:000251695800021
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: On the hardness of minimizing space for all-shortest-path interval routing schemes
Title | On the hardness of minimizing space for all-shortest-path interval routing schemes |
---|---|
Authors | |
Keywords | Compact routing Interval routing schemes NP-completeness |
Issue Date | 2007 |
Publisher | Elsevier 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? |
Abstract | k-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 Identifier | http://hdl.handle.net/10722/89075 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 0.570 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wang, R | en_HK |
dc.contributor.author | Lau, FCM | en_HK |
dc.contributor.author | Liu, YY | en_HK |
dc.date.accessioned | 2010-09-06T09:52:04Z | - |
dc.date.available | 2010-09-06T09:52:04Z | - |
dc.date.issued | 2007 | en_HK |
dc.identifier.citation | Theoretical Computer Science, 2007, v. 389 n. 1-2, p. 250-264 | en_HK |
dc.identifier.issn | 0304-3975 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89075 | - |
dc.description.abstract | k-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.language | eng | en_HK |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs | en_HK |
dc.relation.ispartof | Theoretical Computer Science | en_HK |
dc.rights | Theoretical Computer Science. Copyright © Elsevier BV. | en_HK |
dc.subject | Compact routing | en_HK |
dc.subject | Interval routing schemes | en_HK |
dc.subject | NP-completeness | en_HK |
dc.title | On the hardness of minimizing space for all-shortest-path interval routing schemes | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+Schemes | en_HK |
dc.identifier.email | Lau, FCM:fcmlau@cs.hku.hk | en_HK |
dc.identifier.authority | Lau, FCM=rp00221 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.tcs.2007.09.010 | en_HK |
dc.identifier.scopus | eid_2-s2.0-36049033660 | en_HK |
dc.identifier.hkuros | 138818 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-36049033660&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 389 | en_HK |
dc.identifier.issue | 1-2 | en_HK |
dc.identifier.spage | 250 | en_HK |
dc.identifier.epage | 264 | en_HK |
dc.identifier.isi | WOS:000251695800021 | - |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Wang, R=25653261600 | en_HK |
dc.identifier.scopusauthorid | Lau, FCM=7102749723 | en_HK |
dc.identifier.scopusauthorid | Liu, YY=35248480000 | en_HK |
dc.identifier.issnl | 0304-3975 | - |