The Level Ancestor Problem simplified

Michael A. Bender; Martín Farach-Colton

doi:10.1016/j.tcs.2003.05.002

The Level Ancestor Problem simplified

Michael A. Bender, Martín Farach-Colton

Research output: Contribution to journal › Conference article › peer-review

Abstract

We present a simple algorithm for the Level Ancestor Problem. A Level Ancestor Query LA(v,d) requests the depth d ancestor of node v. The Level Ancestor Problem is to preprocess a given rooted tree T to support level ancestor queries. While optimal solutions to this problem already exist, our new optimal solution is simple enough to be taught and implemented.

Original language	English (US)
Pages (from-to)	5-12
Number of pages	8
Journal	Theoretical Computer Science
Volume	321
Issue number	1
DOIs	https://doi.org/10.1016/j.tcs.2003.05.002
State	Published - Jun 16 2004
Event	Latin American Theoretical Informatics - Cancun, Mexico Duration: Apr 3 2002 → Apr 6 2002

Keywords

Data structures
Level Ancestor Problem
Rooted trees

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2003.05.002

Cite this

@article{e2cfb2ca0d834758a93ea24d459cdd0d,

title = "The Level Ancestor Problem simplified",

abstract = "We present a simple algorithm for the Level Ancestor Problem. A Level Ancestor Query LA(v,d) requests the depth d ancestor of node v. The Level Ancestor Problem is to preprocess a given rooted tree T to support level ancestor queries. While optimal solutions to this problem already exist, our new optimal solution is simple enough to be taught and implemented.",

keywords = "Data structures, Level Ancestor Problem, Rooted trees",

author = "Bender, {Michael A.} and Mart{\'i}n Farach-Colton",

year = "2004",

month = jun,

day = "16",

doi = "10.1016/j.tcs.2003.05.002",

language = "English (US)",

volume = "321",

pages = "5--12",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

note = "Latin American Theoretical Informatics ; Conference date: 03-04-2002 Through 06-04-2002",

}

TY - JOUR

T1 - The Level Ancestor Problem simplified

AU - Bender, Michael A.

AU - Farach-Colton, Martín

PY - 2004/6/16

Y1 - 2004/6/16

N2 - We present a simple algorithm for the Level Ancestor Problem. A Level Ancestor Query LA(v,d) requests the depth d ancestor of node v. The Level Ancestor Problem is to preprocess a given rooted tree T to support level ancestor queries. While optimal solutions to this problem already exist, our new optimal solution is simple enough to be taught and implemented.

AB - We present a simple algorithm for the Level Ancestor Problem. A Level Ancestor Query LA(v,d) requests the depth d ancestor of node v. The Level Ancestor Problem is to preprocess a given rooted tree T to support level ancestor queries. While optimal solutions to this problem already exist, our new optimal solution is simple enough to be taught and implemented.

KW - Data structures

KW - Level Ancestor Problem

KW - Rooted trees

UR - http://www.scopus.com/inward/record.url?scp=2442516025&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=2442516025&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2003.05.002

DO - 10.1016/j.tcs.2003.05.002

M3 - Conference article

AN - SCOPUS:2442516025

SN - 0304-3975

VL - 321

SP - 5

EP - 12

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

T2 - Latin American Theoretical Informatics

Y2 - 3 April 2002 through 6 April 2002

ER -

The Level Ancestor Problem simplified

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this