Optimal node ranking of tree in linear time
From MaRDI portal
Publication:1825031
DOI10.1016/0020-0190(89)90161-0zbMath0683.68038OpenAlexW2092864936WikidataQ56763506 ScholiaQ56763506MaRDI QIDQ1825031
Publication date: 1989
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(89)90161-0
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)
Related Items (50)
A polynomial excluded-minor approximation of treedepth ⋮ An optimal parallel algorithm forc-vertex-ranking of trees ⋮ Vertex ranking of asteroidal triple-free graphs ⋮ Search-space size in contraction hierarchies ⋮ 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 ⋮ NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem ⋮ Graph Bisection with Pareto Optimization ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ Constructing a minimum height elimination tree of a tree in linear time ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ Edge ranking of graphs is hard ⋮ Graphs of bounded depth‐2 rank‐brittleness ⋮ On low tree-depth decompositions ⋮ Grad and classes with bounded expansion. I: Decompositions ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ Unnamed Item ⋮ Rankings of graphs ⋮ On nowhere dense graphs ⋮ Finding the edge ranking number through vertex partitions ⋮ Unnamed Item ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ Polynomial treedepth bounds in linear colorings ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ Computing tree-depth faster than \(2^n\) ⋮ Binary search in graphs revisited ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. ⋮ On the diameter of tree associahedra ⋮ PACE Solver Description: Tree Depth with FlowCutter ⋮ Optimal vertex ranking of block graphs ⋮ Tree-depth, subgraph coloring and homomorphism bounds ⋮ Rank numbers of grid graphs ⋮ On low rank-width colorings ⋮ Maximum matchings of a digraph based on the largest geometric multiplicity ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ The complexity of bicriteria tree-depth ⋮ Hitting sets online and unique-MAX coloring ⋮ The complexity of bicriteria tree-depth ⋮ An optimal parallel algorithm for node ranking of cographs ⋮ Ranking numbers of graphs ⋮ Improved Bounds for the Excluded-Minor Approximation of Treedepth ⋮ Algorithms for generalized vertex-rankings of partial k-trees ⋮ Binary Search in Graphs Revisited ⋮ Unnamed Item ⋮ Counting Homomorphisms to Sparse Graphs ⋮ Diameter estimates for graph associahedra ⋮ Competitive Online Search Trees on Trees ⋮ On vertex ranking of a starlike graph ⋮ An efficient noisy binary search in graphs via Median approximation
Cites Work
This page was built for publication: Optimal node ranking of tree in linear time
