Den Wiener index av en graf är summan av alla pairwise kortaste-path avstånd mellan dess hörn. I detta papper studerar vi det nya problemet med att hitta en minimal Wiener kontakt : med tanke på en ansluten graf G = (V, E) och en uppsättning Q  på frågevertikaler, hitta en subgraf av G som ansluter alla frågevertikaler och har minimal Wiener index. Vi visar att Min Wiener Connector medger en polynom-tid (om än opraktisk) exakt algoritm för specialfallet där antalet frågevertikaler begränsas. Vi visar att i allmänhet problemet är NP-hård, och har ingen PTAS om inte P = NP. Vårt huvudsakliga bidrag är en konstantfaktor approximationsalgoritm som körs i tid O (..) En grundlig experiment på en stor variation av realworld grafer bekräftar att vår metod returnerar mindre och tätare lösningar än andra metoder, och gör det genom att lägga till i frågeuppsättningen Q ett litet antal "viktiga" hörn (dvs hörn med hög centralitet).
Den minsta wiener kontakt problem är att hitta en liten ansluten subgraph för att minimera summan av alla pairwise kortaste-path avstånd mellan de upptäckta hörn REF.
The Minimum Wiener Connector Problem
{'venue': "SIGMOD '15", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}