Edge ranking of graphs is hard

DOI10.1016/S0166-218X(98)00029-8MaRDI QIDQ1392547zbMATH OpenFDO

Authors 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

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

Recommendations

• On an edge ranking problem of trees and graphs
• Minimal hard classes of graphs for the edge list-ranking problem
• Classes of graphs critical for the edge list-ranking problem
• Rankings of Directed Graphs
• Edge search in graphs and hypergraphs of bounded rank
• Optimal edge ranking of complete bipartite graphs in polynomial time
• Ranking by outdegree for directed graphs
• Maximizing the number of edges in optimal \(k\)-rankings
• On the rank of weighted graphs
• scientific article; zbMATH DE number 1262792

Cites work

• Algorithms for generalized vertex-rankings of partial k-trees
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1414315 (Why is no real title available?)
• Local optimization on graphs
• On an edge ranking problem of trees and graphs
• Optimal edge ranking of trees in polynomial time
• Optimal node ranking of tree in linear time
• Optimal node ranking of trees
• Ordered colourings
• Rankings of Directed Graphs
• The NP-Completeness of Edge-Coloring

Cited in

(25)

• Algorithms for generalized vertex-rankings of partial k-trees
• Binary search in graphs revisited
• Finding the edge ranking number through vertex partitions
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• Conflict-free connection of trees
• On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
• (Strong) conflict-free connectivity: algorithm and complexity
• A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs
• Easy and hard instances of arc ranking in directed graphs
• Edge ranking of weighted trees
• Theoretical and complexity results for minimal rankings
• Minimal hard classes of graphs for the edge list-ranking problem
• scientific article; zbMATH DE number 1979519 (Why is no real title available?)
• Facial edge ranking of plane graphs
• Binary search in graphs revisited
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• The complexity of bicriteria tree-depth
• The complexity of bicriteria tree-depth
• A survey on conflict-free connection coloring of graphs
• Ranking numbers of 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
• Edge ranking and searching in partial orders
• Optimal vertex ranking of block graphs

This page was built for publication: Edge ranking of graphs is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1392547)