Jump to ContentJump to Main Navigation
Invitation to Fixed-Parameter Algorithms$
Users without a subscription are not able to see the full content.

Rolf Niedermeier

Print publication date: 2006

Print ISBN-13: 9780198566076

Published to Oxford Scholarship Online: September 2007

DOI: 10.1093/acprof:oso/9780198566076.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2019. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see www.oxfordscholarship.com/page/privacy-policy).date: 19 April 2019

DEPTH-BOUNDED SEARCH TREES

DEPTH-BOUNDED SEARCH TREES

Chapter:
(p.88) 8 DEPTH-BOUNDED SEARCH TREES
Source:
Invitation to Fixed-Parameter Algorithms
Author(s):

Rolf Niedermeier

Publisher:
Oxford University Press
DOI:10.1093/acprof:oso/9780198566076.003.0008

This chapter presents the second very basic design technique for fixed-parameter algorithms: depth-bounded search trees. It starts with simple observations and some basic definitions and facts, including recurrences and branching vectors as a tool for analysing search tree sizes. It continues giving several specific search tree results, including outlines of problems such as Cluster Editing, Vertex Cover, Hitting Set, Closest String, and Dominating Set in Planar Graphs. Moreover, it discusses how to interleave search tree and kernelization procedures to further speed up computation, and it proposes a way to generate automatically search trees (also analysing their sizes) using Cluster Deletion as an illustrative example.

Keywords:   search tree, recurrence, branching vector, Cluster Deletion, automated search tree generation, Cluster Editing, Vertex Cover, Hitting Set, Closest String, Dominating Set in Planar Graphs

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .