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.
| Original language | English |
|---|---|
| Pages (from-to) | 71-86 |
| Journal | Discrete Applied Mathematics |
| Volume | 85 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1 Jun 1998 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Research Keywords
- Approximability
- Computational complexity
- Edge ranking
- Graph labeling algorithms
- NP-completeness
Fingerprint
Dive into the research topics of 'Edge ranking of graphs is hard'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver