Edge ranking of graphs is hard

DOI10.1016/S0166-218X(98)00029-8zbMath0902.68088MaRDI QIDQ1392547

Fung Ling Yue, Tak-Wah Lam

Publication date: 10 December 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

edge rankinggraph labeling algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items

On Dasgupta's hierarchical clustering objective and its relation to other graph parameters, A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs, Minimum edge ranking spanning trees of split graphs, NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, A lower bound for on-line ranking number of a path, Finding the edge ranking number through vertex partitions, On the vertex ranking problem for trapezoid, circular-arc and other graphs, Facial edge ranking of plane graphs, Easy and hard instances of arc ranking in directed graphs, Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, Binary search in graphs revisited, Edge ranking and searching in partial orders, Optimal vertex ranking of block graphs, Edge ranking of weighted trees, (Strong) conflict-free connectivity: algorithm and complexity, The complexity of bicriteria tree-depth, The complexity of bicriteria tree-depth, Conflict-free connection of trees, Ranking numbers of graphs, Algorithms for generalized vertex-rankings of partial k-trees, Binary Search in Graphs Revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On an edge ranking problem of trees and graphs
• Optimal node ranking of trees
• Local optimization on graphs
• Algorithms for generalized vertex-rankings of partial k-trees
• Optimal node ranking of tree in linear time
• Optimal edge ranking of trees in polynomial time
• Ordered colourings
• The NP-Completeness of Edge-Coloring
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Rankings of Directed Graphs