کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431656 | 688602 | 2012 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Path-based supports for hypergraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A path-based support of a hypergraph H is a graph with the same vertex set as H in which each hyperedge induces a Hamiltonian subgraph. While it is NPNP-hard to decide whether a path-based support has a monotone drawing, to determine a path-based support with the minimum number of edges, or to decide whether there is a planar path-based support, we show that a path-based tree support can be computed in polynomial time if it exists.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 14, July 2012, Pages 248–261
Journal: Journal of Discrete Algorithms - Volume 14, July 2012, Pages 248–261
نویسندگان
Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, Arnaud Sallaberry,