Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33A0-1 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33A1-0
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Hagerup, Torben1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-022000
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 518154
Anderer: Local-ID: C1256428004B93B8-7C216E40574881E7C1256A0F004FFA2C-Hagerup2000a
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithmica
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 27 (3/4) Artikelnummer: - Start- / Endseite: 292 - 315 Identifikator: ISSN: 0178-4617