کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
417796 681582 2016 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An ABCABC-Problem for location and consensus functions on graphs
ترجمه فارسی عنوان
یک مسئله ABCABC برای توابع مکان و اجماع بر روی نمودارها
کلمات کلیدی
تابع متوسط؛ تابع محل؛ تابع اجماع؛ رای گیری؛ اصل اجماع؛ مسئله ABCABC
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A location problem can often be phrased as a consensus problem. The median function Med is a location/consensus function on a connected graph GG that has the finite sequences of vertices of GG as input. For each such sequence ππ, Med returns the set of vertices that minimize the distance sum to the elements of ππ. The median function satisfies three intuitively clear axioms: (A)(A) Anonymity, (B)(B) Betweenness and (C)(C) Consistency. Mulder and Novick showed in 2013 that on median graphs these three axioms actually characterize Med. This result raises a number of questions: (i)On what other classes of graphs is Med characterized by (A)(A), (B)(B) and (C)(C)?(ii)If some class of graphs has other ABCABC-functions besides Med, can we determine additional axioms that are needed to characterize Med?(iii)In the latter case, can we find characterizations of other functions that satisfy (A)(A), (B)(B) and (C)(C)?We call these questions, and related ones, the ABCABC-Problem   for consensus functions on graphs. In this paper we present first results. We construct a non-trivial class different from the median graphs, on which the median function is the unique “ABCABC-function”. For the second and third question we focus on KnKn with n≥3n≥3. We construct various non-trivial ABCABC-functions amongst which is an infinite family on K3K3. For some nice families we present a full axiomatic characterization.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 207, 10 July 2016, Pages 15–28
نویسندگان
, , , ,