A linear time algorithm for weighted k-fair domination problem in cactus graphsNovak, Tina (Avtor) Žerovnik, Janez (Avtor) linear algorithmscactus graphsDFS structureweighted k-fair dominationA set D of vertices in a graph G is a k-fair dominating set if every vertex not in D is adjacent to exactly k vertices in D. The weighted k-fair domination number ▫$wfd_k(G)$▫ of a vertex-weighted graph G is the minimum weight w(D) among all k-fair dominating sets D. In addition to the weighted k-fair domination number, some auxiliary parameters are defined. It is shown that for a cactus graph, the weighted k-fair domination number and auxiliary parameters can be calculated in linear time.20222022-09-06 09:49:42Članek v reviji139679UDK: 519.17ISSN pri članku: 2662-2556DOI: 10.1007/s43069-022-00154-8COBISS_ID: 120314883sl