کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872489 | 681651 | 2014 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the subgraph epimorphism problem
ترجمه فارسی عنوان
در مسئله اپیمورفیسم زیرگرافی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اپیمورفیسم زیرگراف، کاهش مدل، فاصله گراف، محدود کردن حل، زیست شناسی سیستم،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we study the problem of deciding the existence of a subgraph epimorphism between two graphs. Our interest in this variant of graph matching problem stems from the study of model reductions in systems biology, where large systems of biochemical reactions can be naturally represented by bipartite digraphs of species and reactions. In this setting, model reduction can be formalized as the existence of a sequence of vertex deletion and merge operations that transforms a first reaction graph into a second graph. This problem is in turn equivalent to the existence of a subgraph (corresponding to delete operations) epimorphism (i.e. surjective homomorphism, corresponding to merge operations) from the first graph to the second. In this paper, we study theoretical properties of subgraph epimorphisms in general directed graphs. We first characterize subgraph epimorphisms (SEPI ), subgraph isomorphisms (SISO ) and graph epimorphisms (EPI ) in terms of graph transformation operations. Then we study the graph distance measures induced by these transformations. We show that they define metrics on graphs and compare them. On the algorithmic side, we show that the SEPI existence problem is NP-complete by reduction of SAT and present a constraint satisfaction algorithm that has been successfully used to solve practical SEPI problems on a large benchmark of reaction graphs from systems biology.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 214-228
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 214-228
نویسندگان
Steven Gay, François Fages, Thierry Martinez, Sylvain Soliman, Christine Solnon,