Algorithms for generalized vertex-rankings of partial k-trees

DOI10.1016/S0304-3975(99)00240-6zbMath0945.68142MaRDI QIDQ1575443

Takao Nishizeki, Xiao Zhou, Md. Abul Kashem

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

algorithm; treewidth; vertex-ranking; partial-tree; separator tree

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

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

Related Items

An optimal parallel algorithm forc-vertex-ranking of trees, Edge ranking of graphs is hard, Algorithms for generalized vertex-rankings of partial k-trees, Finding the edge ranking number through vertex partitions, Fixed-Parameter Tractability of Treewidth and Pathwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On an edge ranking problem of trees and graphs
• Optimal node ranking of trees
• Edge ranking of graphs is hard
• Algorithms for generalized vertex-rankings of partial k-trees
• Optimal node ranking of tree in linear time
• Optimal edge ranking of trees in polynomial time
• Ordered colourings
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• The Role of Elimination Trees in Sparse Factorization
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• Graph minors. II. Algorithmic aspects of tree-width
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Rankings of Graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth