20.500.12556/DKUM-52011 On graph identification problems and the special case of identifying vertices using paths O problemih identifikacije v grafih in o posebnem primeru identifikacije vozlišč s pomočjo poti V članku uvedemo problem identifikacije s potmi: pokritje z identifikacijskimi potmi grafa ▫$G$▫ je množica poti ▫$mathcal{P}$▫, za katere velja, da vsako vozlišče leži na vsaj eni poti iz ▫$mathcal{P}$▫, in za vsak par vozlišč $u,v$ obstaja pot iz ▫$mathcal{P}$▫, ki vsebuje natanko eno izmed vozlišč ▫$u$▫ in ▫$v$▫. Ta problem je soroden raznim variantam identifikacijskih problemov. Problem pokritja z identifikacijskimi potmi obravnavamo na nekaterih družinah grafov. Izpeljemo optimalne velikosti za pokritja z identifikacijskimi potmi za: poti, cikle, hiperkocke in topološka drevesa ter podamo zgornjo mejo za poljubna drevesa. Podamo tudi spodnje in zgornje meje za minimalno velikost pokritja z identifikacijskimi potmi za poljubne grafe in obravnavamo natančnost mej. Pokažemo, da poljuben povezan graf ▫$G$▫ premore pokritje z identifikacijskimi potmi velikosti kvečjemu ▫$Biglceil frac{2(|V(G)|-1)}{3} Bigrceil$▫. Obravnavamo tudi računsko zahtevnost pripadajočega optimizacijskega problema in pokažemo, da v primeru, ko so dolžine poti iz pokritja fiksne dolžine, sodi problem med APX-polne probleme. In this paper, we introduce the identifying path cover problem: an identifying path cover of a graph $G$ is a set ▫$mathcal{P}$▫ of paths such that each vertex belongs to a path of ▫$mathcal{P}$▫, and for each pair ▫$u,v$▫ of vertices, there is a path of ▫$mathcal{P}$▫ which includes exactly one of ▫$u,v$▫. This problem is related to a large variety of identification problems. We investigate the identifying path cover problem in some families of graphs. In particular, we derive the optimal size of an identifying path cover for paths, cycles, hypercubes and topologically irreducible trees and give an upper bound for all trees. We give lower and upper bounds on the minimum size of an identifying path cover for general graphs, and discuss their tightness. In particular, we show that any connected graph ▫$G$▫ has an identifying path cover of size at most ▫$Biglceil frac{2(|V(G)|-1)}{3} Bigrceil$▫. We also study the computational complexity of the associated optimization problem, in particular we show that when the length of the paths is asked to be of a fixed value, the problem is APX-complete. matematika teorija grafov poti aproksimacija mathematics graph theory test cover identification paths approximation true false false Angleški jezik Slovenski jezik Članek v reviji 2015-07-10 15:32:55 2015-07-10 15:32:55 2024-09-25 13:45:56 2019-07-11 07:34:47 2012 0 0 Str. 32-45 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 16584025 16584281 0302-9743 URN:SI:UM:DK:BLPBEJRP http://dx.doi.org/10.1007/978-3-642-35926-2_4 1 https://dk.um.si/Dokument.php?lang=slv&id=76571 Fakulteta za naravoslovje in matematiko 0 0 0