On graph identification problems and the special case of identifying vertices using paths

Foucaud, Florent; Kovše, Matjaž

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	On graph identification problems and the special case of identifying vertices using paths
Avtorji:	ID Foucaud, Florent (Avtor) ID Kovše, Matjaž (Avtor)
Datoteke:	http://dx.doi.org/10.1007/978-3-642-35926-2_4
Jezik:	Angleški jezik
Vrsta gradiva:	Članek v reviji
Tipologija:	1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
Opis:	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.
Ključne besede:	matematika, teorija grafov, poti, aproksimacija, mathematics, graph theory, test cover, identification, paths, approximation
Leto izida:	2012
Št. strani:	Str. 32-45
PID:	20.500.12556/DKUM-52011
UDK:	519.17
COBISS.SI-ID:	16584281
ISSN pri članku:	0302-9743
NUK URN:	URN:SI:UM:DK:BLPBEJRP
Datum objave v DKUM:	10.07.2015
Število ogledov:	1082
Število prenosov:	96
Metapodatki:
Področja:	Ostalo
:	Kopiraj citat

Skupna ocena:	(0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del zbornika

Naslov:	Combinatorial algorithms
COBISS.SI-ID:	16584025

Gradivo je del revije

Naslov:	Lecture notes in computer science
Skrajšan naslov:	Lect. notes comput. sci.
Založnik:	Springer
ISSN:	0302-9743
COBISS.SI-ID:	4292374

Sekundarni jezik

Jezik:	Slovenski jezik
Naslov:	O problemih identifikacije v grafih in o posebnem primeru identifikacije vozlišč s pomočjo poti
Opis:	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.

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj