Edge ranking of weighted trees

DOI10.1016/J.DAM.2005.11.005MaRDI QIDQ2495900zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski

Publication date 30 June 2006

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

Full work available at URL https://doi.org/10.1016/j.dam.2005.11.005

zbMATH Keywords

approximationedge rankingmultigraphNP-completenesspolynomial algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 975401
• Publication:4886041
• On an edge ranking problem of trees and graphs
• On minimum edge ranking spanning trees
• scientific article; zbMATH DE number 437538

Cites work

• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Edge ranking of graphs is hard
• 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 1979519 (Why is no real title available?)
• scientific article; zbMATH DE number 5033869 (Why is no real title available?)
• On an edge ranking problem of trees and graphs
• On minimum edge ranking spanning trees
• Optimal edge ranking of trees in polynomial time
• Optimal node ranking of trees

Cited in

(16)

• The binary identification problem for weighted trees
• Finding the edge ranking number through vertex partitions
• Easy and hard instances of arc ranking in directed graphs
• On minimum edge ranking spanning trees
• On the tree search problem with non-uniform costs
• On the tree search problem with non-uniform costs
• Facial edge ranking of plane graphs
• Critical hereditary graph classes: a survey
• The complexity of bicriteria tree-depth
• The complexity of bicriteria tree-depth
• Edge and pair queries-random graphs and complexity
• On the complexity of searching in trees and partially ordered structures
• Partial order multiway search
• On an edge ranking problem of trees and graphs
• Vertex rankings of chordal graphs and weighted trees
• Edge ranking and searching in partial orders

This page was built for publication: Edge ranking of weighted trees

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