کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439058 690428 2010 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
NP-Completeness of st-orientations for plane graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
NP-Completeness of st-orientations for plane graphs
چکیده انگلیسی

An st-orientation or bipolar orientation of a 2-connected graph G is an orientation of its edges to generate a directed acyclic graph with a single source s and a single sink t. Given a plane graph G and two exterior vertices s and t, the problem of finding an optimum st-orientation, i.e., an st-orientation in which the length of a longest st-path is minimized, was first proposed indirectly by Rosenstiehl and Tarjan in and then later directly by He and Kao in . In this paper, we prove that, given a 2-connected plane graph G, two exterior vertices s, t, and a positive integer K, the decision problem of whether G has an st-orientation, where the maximum length of an st-path is ≤K, is NP-Complete. This solves a long standing open problem on the complexity of optimum st-orientations for plane graphs. As a by-product, we prove that the NP-Completeness result holds for planar graphs as well.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 411, Issues 7–9, 28 February 2010, Pages 995-1003