Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich.
mehr Informationen...
Journal of algorithms, 1991-06, Vol.12 (2), p.308-340
Ort / Verlag
San Diego, CA: Elsevier Inc
Erscheinungsjahr
1991
Link zum Volltext
Quelle
Elsevier Journal Backfiles on ScienceDirect (DFG Nationallizenzen)
Beschreibungen/Notizen
Using a variation of the interpretability concept we show that all graph properties definable in monadic second-order logic (MS properties) with quantification over vertex and edge sets can be decided in linear time for classes of graphs of fixed bounded treewidth given a tree-decomposition. This gives an alternative proof of a recent result by Courcelle. We allow graphs with directed and/or undirected edges, labeled on edges and/or vertices with labels taken from a finite set. We extend MS properties to extended monadic second-order (EMS) problems involving counting or summing evaluations over sets definable in monadic second-order logic. Our technique allows us also to solve some EMS problems in linear time or in polynomial or pseudopolynomial time for classes of graphs of fixed bounded treewidth. Moreover, it is shown that each EMS problem is in NC for graphs of bounded treewidth. Most problems for which linear time algorithms for graphs of bounded treewidth were previously known to exist, and many others, are EMS problems.