Algorithmic Meta-Theorems

Details Algorithmic Meta-Theorems Algorithmic Meta-Theorems

2009-02-20

arxiv.org/abs/0902.3616v1

Computer Science

Logic in Computer Science

Scientific paper

Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a "logical" and a "structural" component, that is they are results of the form: every computational problem that can be formalised in a given logic L can be solved efficiently on every class C of structures satisfying certain conditions. This paper gives a survey of algorithmic meta-theorems obtained in recent years and the methods used to prove them. As many meta-theorems use results from graph minor theory, we give a brief introduction to the theory developed by Robertson and Seymour for their proof of the graph minor theorem and state the main algorithmic consequences of this theory as far as they are needed in the theory of algorithmic meta-theorems.

Affiliated with

Also associated with

No associations

Rating

Algorithmic Meta-Theorems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithmic Meta-Theorems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmic Meta-Theorems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-671499