کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
471215 698607 2008 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Locally constrained graph homomorphisms—structure, complexity, and applications
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Locally constrained graph homomorphisms—structure, complexity, and applications
چکیده انگلیسی

A graph homomorphism is an edge preserving vertex mapping between two graphs. Locally constrained homomorphisms are those that behave well on the neighborhoods of vertices. If the neighborhood of any vertex of the source graph is mapped bijectively (injectively, surjectively) to the neighborhood of its image in the target graph, the homomorphism is called locally bijective (injective, surjective, respectively). We show that this view unifies issues studied before from different perspectives and under different names, such as graph covers, distance constrained graph labelings, or role assignments. Our survey provides an overview of applications, complexity results, related problems, and historical notes on locally constrained graph homomorphisms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Science Review - Volume 2, Issue 2, August 2008, Pages 97–111
نویسندگان
, ,