کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872473 | 681651 | 2014 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Automated generation of conjectures on forbidden subgraph characterization
ترجمه فارسی عنوان
تولید نسبی فکری بر خصوصیات زیرگرافی ممنوع
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نظریه گراف، خصوصیات زیرگرافی ممنوع نسل گمشده اتوماتیک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a class of graphs F, a forbidden subgraph characterization (FSC) is a set of graphs H such that a graph G belongs to F if and only if no graph of H is isomorphic to an induced subgraph of G. FSCs play a key role in graph theory, and are at the center of many important results obtained in that field. In this paper, we present novel methods that automate the generation of conjectures on FSCs. Since most classes of graphs do not have such characterization, we also describe methods to find less restrictive results in the form of necessary or sufficient conditions to characterize a class of graphs with forbidden subgraphs. Furthermore, while these methods require to explore a possibly infinite search space, we present an enumerative technique that guarantees the discovery of characterizations involving forbidden subgraphs with a limited number of vertices. Another technique, which enables the discovery of characterizations with much larger subgraphs through the use of a heuristic search, is also described. In our experiments, we use these methods to find new theorems on the characterization of well-known graph classes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 177-194
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 177-194
نویسندگان
Christian Desrosiers, Philippe Galinier, Pierre Hansen, Alain Hertz,