Motiverade av utmaningar relaterade till dominans, konnektivitet och informationsspridning i sociala och andra nätverk inleder vi studiet av problemet Vector Connectivity. Detta problem tar som inmatning en graf G och ett heltal kv för varje vertex v av G, och målet är att hitta en vertex delmängd S av minsta kardinalitet sådan att varje vertex v antingen tillhör S, eller är ansluten till åtminstone kv hörn av S genom dishead banor. Om vi kräver att varje väg ska vara av längd exakt 1, vi * En utökad abstrakt av denna tidning dök upp i förfarandet av den 10: e årliga Con-1 få den välkända Vector Domination problem, som är en generalisering av den berömda Dominating Set problem och flera av dess varianter. Följaktligen blir vårt problem NP-hårdt om en övre gräns på längden av de delade vägarna också levereras som ingång. På grund av hårdheten hos dessa dominansvarianter även på begränsade graf klasser, som split grafer, Vector Connectivity verkar vara ett naturligt problem att studera för att rita gränserna för dragbarhet för denna typ av problem. Vi visar att Vector Connectivity faktiskt kan lösas i polynom tid på delade grafer, förutom cographs och träd. Vi visar också att problemet kan approximeras i polynom tid inom en faktor av ln n + 2 på alla n-vertex grafer.
Studien av problemet med Vector Connectivity initierades av Boros et al. REF som gav polynom-tidsalgoritmer för träd, cographs och delade grafer.
Vector connectivity in graphs
{'venue': 'Networks', 'journal': 'Networks', 'mag_field_of_study': ['Mathematics', 'Computer Science']}