Optimal node ranking of trees
From MaRDI portal
Publication:1113677
DOI10.1016/0020-0190(88)90194-9zbMath0661.68063OpenAlexW2082764577WikidataQ56763504 ScholiaQ56763504MaRDI QIDQ1113677
H. Donald Ratliff, Ananth V. Iyer, Gopalakrishnan Vijayan
Publication date: 1988
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(88)90194-9
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)
Related Items (43)
List rankings and on-line list rankings of graphs ⋮ Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs ⋮ An optimal parallel algorithm forc-vertex-ranking of trees ⋮ On Dasgupta's hierarchical clustering objective and its relation to other graph parameters ⋮ Optimal edge ranking of trees in polynomial time ⋮ A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs ⋮ Ordered colourings ⋮ Maximum value of conflict-free vertex-connection number of graphs ⋮ NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ A lower bound for on-line ranking number of a path ⋮ Graph Bisection with Pareto Optimization ⋮ Constructing a minimum height elimination tree of a tree in linear time ⋮ Edge ranking of graphs is hard ⋮ Uniqueness and minimal obstructions for tree-depth ⋮ Rankings of graphs ⋮ Graph unique-maximum and conflict-free colorings ⋮ Finding the edge ranking number through vertex partitions ⋮ Ordered coloring of grids and related graphs ⋮ Unnamed Item ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ Rank numbers for bent ladders ⋮ Easy and hard instances of arc ranking in directed graphs ⋮ Binary search in graphs revisited ⋮ Graphs with large rank numbers and rank numbers of subdivided stars ⋮ Edge ranking and searching in partial orders ⋮ On 1-uniqueness and dense critical graphs for tree-depth ⋮ Optimal vertex ranking of block graphs ⋮ Edge ranking of weighted trees ⋮ Rank numbers of grid graphs ⋮ Rank numbers for some trees and unicyclic graphs ⋮ Greedy rankings and arank numbers ⋮ Conflict-free vertex-connections of graphs ⋮ The complexity of bicriteria tree-depth ⋮ Hitting sets online and unique-MAX coloring ⋮ An optimal parallel algorithm for node ranking of cographs ⋮ Ranking numbers of graphs ⋮ Optimal node ranking of tree in linear time ⋮ Ordered Coloring Grids and Related Graphs ⋮ Algorithms for generalized vertex-rankings of partial k-trees ⋮ Binary Search in Graphs Revisited ⋮ On vertex rankings of graphs and its relatives ⋮ On an edge ranking problem of trees and graphs
Cites Work
This page was built for publication: Optimal node ranking of trees
