I detta dokument introduceras begreppet informativa märkningssystem för godtyckliga diagram. Låt f (W ) vara en funktion på undergrupper av hörn W. En f märkning system etiketter hörn av en viktad graf G på ett sådant sätt att f (W ) kan härledas (eller åtminstone ungefärlig) effektivt för någon vertex delmängd W av G genom att bara inspektera etiketter av hörn av W, utan att behöva använda några ytterligare informationskällor. Ett antal resultat som illustrerar detta begrepp presenteras i dokumentet. Vi börjar med att utveckla f-märkningssystem för tre funktioner f över klassen n-vertex träd. Den första funktionen, SepLevel, ger separationsnivån för två hörn i trädet, nämligen djupet av deras minsta gemensamma förfader. Den andra, LCA, ger den minst vanliga förfadern till två hörn. Den tredje, Center, ger centrum för alla tre givna hörn v 1, v 2, v 3 i trädet, nämligen den unika vertex z ansluten till dem genom tre kant-avskiljande vägar. Alla dessa tre märkningssystem använder O(log 2 n)-bitars-etiketter, som visas vara asymptotiskt optimala. Våra viktigaste resultat gäller funktionen Steiner(W ), definierad för viktade grafer. För varje vertex delmängd W i den viktade grafen G representerar Steiner(W ) vikten av Steiner-trädet som spänner över hörnen av W i G. Med tanke på klassen n-vertexträd med M-bitars kantvikter, visas det att det för denna klass finns ett Steiner-märkningsschema med hjälp av O((M + log n) log n) bitetiketter, vilket är asymptotiskt optimalt. Det visas sedan att det för klassen godtyckliga n-vertexgrafer med M-bitars kantvikter finns ett ungefärligt Steiner-märkningssystem som ger en uppskattning (upp till en faktor för O(log n)) för Steinervikt Steiner(W ) för en given uppsättning hörn W, med hjälp av O((M + log n)log 2 n) bitetiketter.
Ett statiskt märkningssystem för den id-baserade närmaste gemensamma förfadern (NCA) relationen på träd har utvecklats i REF med hjälp av etiketter på  påslag (log 2 n) på n-node träd.
Informative labeling schemes for graphs
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}