Algorithms for generalized vertex-rankings of partial k-trees

DOI10.1016/S0304-3975(99)00240-6MaRDI QIDQ1575443zbMATH OpenFDO

Authors Md. Abul Kashem, Xiao Zhou, Takao Nishizeki

Publication date 21 August 2000

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

zbMATH Keywords

algorithmtreewidthvertex-rankingpartial-treeseparator tree

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1088275
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• scientific article; zbMATH DE number 4094838
• Algorithms and Computation
• An optimal parallel algorithm forc-vertex-ranking of trees
• Practical algorithms on partial k-trees with an application to domination-like problems
• scientific article; zbMATH DE number 4008409
• Vertex partitioning problems on partial k-trees
• Improved algorithms for ranking and unranking \((k, m)\)-ary trees in B-order

Cites work

• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1303585 (Why is no real title available?)
• scientific article; zbMATH DE number 1088275 (Why is no real title available?)
• scientific article; zbMATH DE number 1142299 (Why is no real title available?)
• scientific article; zbMATH DE number 1414315 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms for generalized vertex-rankings of partial k-trees
• Edge ranking of graphs is hard
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• On an edge ranking problem of trees and graphs
• Optimal edge ranking of trees in polynomial time
• Optimal node ranking of tree in linear time
• Optimal node ranking of trees
• Ordered colourings
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Rankings of Graphs
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• The Role of Elimination Trees in Sparse Factorization
• Vertex ranking of asteroidal triple-free graphs

Cited in

(17)

• Parallel Processing and Applied Mathematics
• An optimal parallel algorithm forc-vertex-ranking of trees
• Algorithms for generalized vertex-rankings of partial k-trees
• Finding the edge ranking number through vertex partitions
• Vertex rankings of chordal graphs and weighted trees
• Optimal vertex ranking of block graphs
• scientific article; zbMATH DE number 1414315 (Why is no real title available?)
• Comparing linear width parameters for directed graphs
• Fixed-parameter algorithms for Kemeny rankings
• Vertex ranking with capacity
• Algorithms and Computation
• scientific article; zbMATH DE number 1088275 (Why is no real title available?)
• How to compute digraph width measures on directed co-graphs
• Parameterized top-\(K\) algorithms
• The behavior of clique-width under graph operations and graph transformations
• Edge ranking of graphs is hard
• Fixed-parameter tractability of treewidth and pathwidth

This page was built for publication: Algorithms for generalized vertex-rankings of partial k-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1575443)