Edge and node searching problems on trees

DOI10.1016/S0304-3975(99)00241-8MaRDI QIDQ1575444zbMATH OpenOpenAlexFDO

Authors N. Delaunay

Publication date 21 August 2000

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

Full work available at URL https://doi.org/10.1016/s0304-3975(99)00241-8

zbMATH Keywords

treealgorithmpathwidthedge searchingnode searching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 1222842
• On the Fast Searching Problem
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Connected searching of weighted trees

Cites work

• scientific article; zbMATH DE number 4173000 (Why is no real title available?)
• scientific article; zbMATH DE number 4174651 (Why is no real title available?)
• scientific article; zbMATH DE number 3650583 (Why is no real title available?)
• scientific article; zbMATH DE number 4202053 (Why is no real title available?)
• scientific article; zbMATH DE number 4144015 (Why is no real title available?)
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 3819512 (Why is no real title available?)
• scientific article; zbMATH DE number 4105017 (Why is no real title available?)
• scientific article; zbMATH DE number 125491 (Why is no real title available?)
• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• A polynomial algorithm for the min-cut linear arrangement of trees
• Complexity of Finding Embeddings in a k-Tree
• Edge and node searching problems on trees
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Graph minors. I. Excluding a forest
• Graph searching on chordal graphs
• Interval graphs and searching
• Min Cut is NP-complete for edge weighted trees
• Monotonicity in graph searching
• Narrowness, pathwidth, and their application in natural language processing
• On minimizing width in linear layouts
• On the pathwidth of chordal graphs
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• Recontamination does not help to search a graph
• Searching and pebbling
• The Pathwidth and Treewidth of Cographs
• The complexity of searching a graph
• The vertex separation and search number of a graph
• The vertex separation number of a graph equals its path-width
• Topological Bandwidth
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth. Computations and approximations

Cited in

(18)

• A distributed algorithm for computing the node search number in trees
• Pathwidth is NP-Hard for Weighted Trees
• A pathfinding problem for search trees with unknown edge length
• Edge search number of cographs
• Minimal trees of a given search number
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Constrained graph searching on trees
• Connected searching of weighted trees
• Searching Trees with Sources and Targets
• scientific article; zbMATH DE number 1670677 (Why is no real title available?)
• Edge and node searching problems on trees
• An annotated bibliography on guaranteed graph searching
• Exclusive graph searching
• Connected searching of weighted trees
• scientific article; zbMATH DE number 146433 (Why is no real title available?)
• Mixed Search Number of Permutation Graphs
• Node-searching problem on block graphs
• Edge Search Number of Cographs in Linear Time

This page was built for publication: Edge and node searching problems on trees

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