File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Scopus: eid_2-s2.0-0039571998
- WOS: WOS:000074234500005
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Edge ranking of graphs is hard
Title | Edge ranking of graphs is hard |
---|---|
Authors | |
Keywords | Approximability Computational complexity Edge ranking Graph labeling algorithms NP-completeness |
Issue Date | 1998 |
Publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/dam |
Citation | Discrete Applied Mathematics, 1998, v. 85 n. 1, p. 71-86 How to Cite? |
Abstract | An edge ranking of a graph is a restricted coloring of the edges with integers. It requires that every path between two edges with the same label i contains an intermediate edge with label j > i. An edge ranking is optimal if it uses the least number of distinct labels among all possible edge rankings. Recent research has revealed that the problem of finding an optimal edge ranking when restricted to trees admits a polynomial-time solution, yet the complexity of the problem for general graphs has remained open in the literature. In this paper, we prove that finding an optimal edge ranking of a graph is NP-hard. Also, we show that even finding a reasonably small edge ranking is infeasible in some cases. © 1998 Elsevier Science B.V. All rights reserved. |
Persistent Identifier | http://hdl.handle.net/10722/88984 |
ISSN | 2023 Impact Factor: 1.0 2023 SCImago Journal Rankings: 0.657 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Yue, FL | en_HK |
dc.date.accessioned | 2010-09-06T09:50:56Z | - |
dc.date.available | 2010-09-06T09:50:56Z | - |
dc.date.issued | 1998 | en_HK |
dc.identifier.citation | Discrete Applied Mathematics, 1998, v. 85 n. 1, p. 71-86 | en_HK |
dc.identifier.issn | 0166-218X | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/88984 | - |
dc.description.abstract | An edge ranking of a graph is a restricted coloring of the edges with integers. It requires that every path between two edges with the same label i contains an intermediate edge with label j > i. An edge ranking is optimal if it uses the least number of distinct labels among all possible edge rankings. Recent research has revealed that the problem of finding an optimal edge ranking when restricted to trees admits a polynomial-time solution, yet the complexity of the problem for general graphs has remained open in the literature. In this paper, we prove that finding an optimal edge ranking of a graph is NP-hard. Also, we show that even finding a reasonably small edge ranking is infeasible in some cases. © 1998 Elsevier Science B.V. 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/dam | en_HK |
dc.relation.ispartof | Discrete Applied Mathematics | en_HK |
dc.rights | Discrete Applied Mathematics. Copyright © Elsevier BV. | en_HK |
dc.subject | Approximability | en_HK |
dc.subject | Computational complexity | en_HK |
dc.subject | Edge ranking | en_HK |
dc.subject | Graph labeling algorithms | en_HK |
dc.subject | NP-completeness | en_HK |
dc.title | Edge ranking of graphs is hard | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0166-218X&volume=85:1&spage=71&epage=86&date=1998&atitle=Edge+ranking+of+graphs+is+hard | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-0039571998 | en_HK |
dc.identifier.hkuros | 40764 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0039571998&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 85 | en_HK |
dc.identifier.issue | 1 | en_HK |
dc.identifier.spage | 71 | en_HK |
dc.identifier.epage | 86 | en_HK |
dc.identifier.isi | WOS:000074234500005 | - |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Yue, FL=7004029949 | en_HK |
dc.identifier.issnl | 0166-218X | - |