Edge and node searching problems on trees

Sheng Lung Peng, Chin Wen Ho, Tsan Sheng Hsu, Ming Tat Ko, Chuan Yi Tang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

In this paper, we show that there is a natural correspondence between a tree's edge-search strategy and its node-search strategy. By doing so, we simplify the previous linear time algorithm for determining the edge-search number of a tree, and improve the running time of a previous algorithm for constructing an edge-search strategy (or plan) for a tree containing n vertices from O(n log n) to O(n) time.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings
EditorsTao Jiang, D.T. Lee
PublisherSpringer Verlag
Pages284-293
Number of pages10
ISBN (Print)354063357X, 9783540633570
DOIs
StatePublished - 1997
Event3rd Annual International Computing and Combinatorics Conference, COCOON 1997 - Shanghai, China
Duration: 20 Aug 199722 Aug 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1276
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd Annual International Computing and Combinatorics Conference, COCOON 1997
Country/TerritoryChina
CityShanghai
Period20/08/9722/08/97

Fingerprint

Dive into the research topics of 'Edge and node searching problems on trees'. Together they form a unique fingerprint.

Cite this