Rankings of Graphs
From MaRDI portal
Publication:4388986
DOI10.1137/S0895480195282550zbMath0907.68137MaRDI QIDQ4388986
Dieter Kratsch, Ton Kloks, Haiko Müller, Jitender S. Deogun, Zsolt Tuza, Klaus Jansen, Hans L. Bodlaender
Publication date: 11 May 1998
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (68)
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 ⋮ Vertex ranking of asteroidal triple-free graphs ⋮ Safe sets in graphs: graph classes and structural parameters ⋮ On Dasgupta's hierarchical clustering objective and its relation to other graph parameters ⋮ Vertex rankings of chordal graphs and weighted trees ⋮ A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs ⋮ THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS ⋮ Extrema property of the \(k\)-ranking of directed paths and cycles ⋮ Minimum edge ranking spanning trees of split graphs ⋮ NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem ⋮ Characterizing width two for variants of treewidth ⋮ The complexity of restricted star colouring ⋮ A lower bound for on-line ranking number of a path ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ Greedy algorithms for generalized \(k\)-rankings of paths ⋮ Constructing a minimum height elimination tree of a tree in linear time ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ Effective computation of immersion obstructions for unions of graph classes ⋮ Graphs of bounded depth‐2 rank‐brittleness ⋮ Maximizing the number of edges in optimal \(k\)-rankings ⋮ Forbidden graphs for tree-depth ⋮ On low tree-depth decompositions ⋮ Safe Sets in Graphs: Graph Classes and Structural Parameters ⋮ Uniqueness and minimal obstructions for tree-depth ⋮ Efficient interprocedural data-flow analysis using treedepth and treewidth ⋮ Graph unique-maximum and conflict-free colorings ⋮ Finding the edge ranking number through vertex partitions ⋮ Ordered coloring of grids and related graphs ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ Arankings of trees ⋮ Rank numbers for bent ladders ⋮ Polynomial treedepth bounds in linear colorings ⋮ Computing tree-depth faster than \(2^n\) ⋮ Facial edge ranking of plane graphs ⋮ Easy and hard instances of arc ranking in directed graphs ⋮ On the diameter of tree associahedra ⋮ A survey and classification of Sierpiński-type graphs ⋮ On 1-uniqueness and dense critical graphs for tree-depth ⋮ Optimal vertex ranking of block graphs ⋮ PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA ⋮ Minimal \(k\)-rankings and the rank number of \(P^2_n\) ⋮ Rank numbers of grid graphs ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ Minimal rankings and the arank number of a path ⋮ Rank numbers for some trees and unicyclic graphs ⋮ On low rank-width colorings ⋮ (Strong) conflict-free connectivity: algorithm and complexity ⋮ Maximum matchings of a digraph based on the largest geometric multiplicity ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Brooks type results for conflict-free colorings and \(\{a, b \}\)-factors in graphs ⋮ The complexity of bicriteria tree-depth ⋮ The complexity of bicriteria tree-depth ⋮ Conflict-free connection of trees ⋮ Elimination Distance to Bounded Degree on Planar Graphs ⋮ Non-monochromatic and conflict-free colorings on tree spaces and planar network spaces ⋮ Max-optimal and sum-optimal labelings of graphs ⋮ Ranking numbers of graphs ⋮ Biconvex graphs: Ordering and algorithms ⋮ Descriptional complexity of regular languages ⋮ Algorithms for generalized vertex-rankings of partial k-trees ⋮ Unnamed Item ⋮ Obstructions for Tree-depth ⋮ Diameter estimates for graph associahedra ⋮ On vertex rankings of graphs and its relatives ⋮ Competitive Online Search Trees on Trees
This page was built for publication: Rankings of Graphs
