English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Dynamic algorithms for graphs of bounded treewidth

Hagerup, T. (2000). Dynamic algorithms for graphs of bounded treewidth. Algorithmica, 27(3/4), 292-315.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Hagerup, Torben1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: The formalism of monadic second-order (MS) logic has been very successful in unifying a large number of algorithms for graphs of bounded treewidth. We extend the elegant framework of MS logic from static problems to dynamic problems, in which queries about MS properties of a graph of bounded treewidth are interspersed with updates of vertex and edge labels. This allows us to unify and occasionally strengthen a number of scattered previous results obtained in an ad hoc manner and to enable solutions to a wide range of additional problems to be derived automatically. As an auxiliary result of independent interest, we dynamize a data structure of Chazelle for answering queries about products of labels along paths in a tree with edges labeled by elements of a semigroup.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-022000
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 518154
Other: Local-ID: C1256428004B93B8-7C216E40574881E7C1256A0F004FFA2C-Hagerup2000a
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithmica
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 27 (3/4) Sequence Number: - Start / End Page: 292 - 315 Identifier: ISSN: 0178-4617