Logic, Graphs, and Algorithms

@techreport{citeulike:1693353, abstract = {Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic can be decided in linear time on graphs of bounded tree width. This article is an introduction into the theory underlying such meta theorems and a survey of the most important results in this area.}, author = {Grohe, Martin }, citeulike-article-id = {1693353}, institution = {Electronic Colloquium on Computational Complexity}, keywords = {algorithms, complexity, graph, logic}, posted-at = {2007-09-25 17:10:00}, priority = {5}, series = {ECCC Report TR07-091}, title = {Logic, Graphs, and Algorithms}, url = {http://eccc.hpi-web.de/eccc-reports/2007/TR07-091/index.html}, year = {2007} }

TY - RPRT ID - citeulike:1693353 L3 - citeulike-article-id:1693353 TI - Logic, Graphs, and Algorithms SE - ECCC Report TR07-091 N2 - Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic can be decided in linear time on graphs of bounded tree width. This article is an introduction into the theory underlying such meta theorems and a survey of the most important results in this area. KW - algorithms KW - complexity KW - graph KW - logic AU - Grohe, Martin PY - 2007/// UR - http://eccc.hpi-web.de/eccc-reports/2007/TR07-091/index.html ER -