On the vertex ranking problem for trapezoid, circular-arc and other graphs

DOI10.1016/S0166-218X(99)00179-1zbMath0937.68093DBLPjournals/dam/DeogunKKM99WikidataQ56764983 ScholiaQ56764983MaRDI QIDQ1961233

Haiko Müller, Jitender S. Deogun, Dieter Kratsch, Ton Kloks

Publication date: 17 January 2000

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

zbMATH Keywords

graph classesvertex ranking problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (23)

Disconnected matchings ⋮ An optimal parallel algorithm forc-vertex-ranking of trees ⋮ 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 ⋮ NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ A lower bound for on-line ranking number of a path ⋮ Constructing a minimum height elimination tree of a tree in linear time ⋮ On the hardness of inclusion-wise minimal separators enumeration ⋮ Finding the edge ranking number through vertex partitions ⋮ Unnamed Item ⋮ Computing tree-depth faster than \(2^n\) ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. ⋮ On the diameter of tree associahedra ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ Optimal vertex ranking of block graphs ⋮ Rank numbers of grid graphs ⋮ On the size of minimal separators for treedepth decomposition ⋮ Disconnected matchings ⋮ Ranking numbers of graphs ⋮ Ordered Coloring Grids and Related Graphs ⋮ Competitive Online Search Trees on Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex ranking of asteroidal triple-free graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• On an edge ranking problem of trees and graphs
• Optimal node ranking of trees
• Complement reducible graphs
• On a graph partition problem with application to VLSI layout
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Treewidth. Computations and approximations
• Finding minimum height elimination trees for interval graphs in polynomial time
• Edge ranking of graphs is hard
• Optimal node ranking of tree in linear time
• Optimal edge ranking of trees in polynomial time
• Ordered colourings
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The Role of Elimination Trees in Sparse Factorization
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• The Complexity of the Partial Order Dimension Problem
• Minimum Fill-in on Circle and Circular-Arc Graphs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• On the 2-Chain Subgraph Cover and Related Problems
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Asteroidal Triple-Free Graphs
• Rankings of Graphs
• Treewidth and Pathwidth of Permutation Graphs

This page was built for publication: On the vertex ranking problem for trapezoid, circular-arc and other graphs