File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Edge ranking of graphs is hard

TitleEdge ranking of graphs is hard
Authors
Lam, TWYue, FL
KeywordsApproximability
Computational complexity
Edge ranking
Graph labeling algorithms
NP-completeness
Issue Date1998
PublisherElsevier 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?
AbstractAn 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 Identifierhttp://hdl.handle.net/10722/88984
ISSN
0166-218X
2023 Impact Factor: 1.0
2023 SCImago Journal Rankings: 0.657
ISI Accession Number ID
WOS:000074234500005
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorYue, FLen_HK
dc.date.accessioned2010-09-06T09:50:56Z-
dc.date.available2010-09-06T09:50:56Z-
dc.date.issued1998en_HK
dc.identifier.citationDiscrete Applied Mathematics, 1998, v. 85 n. 1, p. 71-86en_HK
dc.identifier.issn0166-218Xen_HK
dc.identifier.urihttp://hdl.handle.net/10722/88984-
dc.description.abstractAn 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.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/damen_HK
dc.relation.ispartofDiscrete Applied Mathematicsen_HK
dc.rightsDiscrete Applied Mathematics. Copyright © Elsevier BV.en_HK
dc.subjectApproximabilityen_HK
dc.subjectComputational complexityen_HK
dc.subjectEdge rankingen_HK
dc.subjectGraph labeling algorithmsen_HK
dc.subjectNP-completenessen_HK
dc.titleEdge ranking of graphs is harden_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://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+harden_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-0039571998en_HK
dc.identifier.hkuros40764en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0039571998&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume85en_HK
dc.identifier.issue1en_HK
dc.identifier.spage71en_HK
dc.identifier.epage86en_HK
dc.identifier.isiWOS:000074234500005-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridYue, FL=7004029949en_HK
dc.identifier.issnl0166-218X-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats