Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Hagerup, Torben

dblp



BibTeX cite key*:

Hagerup2000a

Title

Title*:

Dynamic algorithms for graphs of bounded treewidth

Journal

Journal Title*:

Algorithmica

Journal's URL:

http://link.springer-ny.com/link/service/journals/00453/

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer-ny.com/

Publisher's
Address:

New York, USA

ISSN:

0178-4617

Vol, No, pp, Date

Volume*:

27

Number:

3/4

Publishing Date:

2000

Pages*:

292-315

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Hagerup2000a,
AUTHOR = {Hagerup, Torben},
TITLE = {Dynamic algorithms for graphs of bounded treewidth},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2000},
NUMBER = {3/4},
VOLUME = {27},
PAGES = {292--315},
ADDRESS = {New York, USA},
ISBN = {0178-4617},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Anja Becker
Created
03/14/2001 03:33:33 PM
Revision
1.
0.


Editor
Uwe Brahm
Anja Becker


Edit Date
05/02/2001 11:28:11 AM
14.03.2001 15:35:44