کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421963 684994 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Switching Graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Switching Graphs
چکیده انگلیسی

Switching graphs are graphs containing switches. By using boolean functions called switch settings, these switches can be put in a fixed direction to obtain an ordinary graph. For many problems, switching graphs are a remarkable straightforward and natural model, but they have hardly been studied. We study the complexity of several natural questions in switching graphs of which some are polynomial, and others are NP-complete. We started investigating switching graphs because they turned out to be a natural framework for studying the problem of solving Boolean equation systems, which is equivalent to model checking of the modal μ-calculus and deciding the winner in parity games. We give direct, polynomial encodings of Boolean equation systems in switching graphs and vice versa, and prove correctness of the encodings.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 223, 26 December 2008, Pages 119-135