کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328736 | 684878 | 2005 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs](/preview/png/10328736.png)
چکیده انگلیسی
This paper deals with the graph isomorphism (GI) problem for two graph classes: chordal bipartite graphs and strongly chordal graphs. It is known that GI problem is GI complete even for some special graph classes including regular graphs, bipartite graphs, chordal graphs, comparability graphs, split graphs, and k-trees with unbounded k. On the other hand, the relative complexity of the GI problem for the above classes was unknown. We prove that deciding isomorphism of the classes are GI complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 145, Issue 3, 30 January 2005, Pages 479-482
Journal: Discrete Applied Mathematics - Volume 145, Issue 3, 30 January 2005, Pages 479-482
نویسندگان
Ryuhei Uehara, Seinosuke Toda, Takayuki Nagoya,