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

Foucaud, Florent; Kovše, Matjaž

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	On graph identification problems and the special case of identifying vertices using paths
Authors:	ID Foucaud, Florent (Author) ID Kovše, Matjaž (Author)
Files:	http://dx.doi.org/10.1007/978-3-642-35926-2_4
Language:	English
Work type:	Article
Typology:	1.08 - Published Scientific Conference Contribution
Organization:	FNM - Faculty of Natural Sciences and Mathematics
Abstract:	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.
Keywords:	matematika, teorija grafov, poti, aproksimacija, mathematics, graph theory, test cover, identification, paths, approximation
Year of publishing:	2012
Number of pages:	Str. 32-45
PID:	20.500.12556/DKUM-52011
UDC:	519.17
ISSN on article:	0302-9743
COBISS.SI-ID:	16584281
NUK URN:	URN:SI:UM:DK:BLPBEJRP
Publication date in DKUM:	10.07.2015
Views:	1081
Downloads:	96
Metadata:
Categories:	Misc.
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a proceedings

Title:	Combinatorial algorithms
COBISS.SI-ID:	16584025

Record is a part of a journal

Title:	Lecture notes in computer science
Shortened title:	Lect. notes comput. sci.
Publisher:	Springer
ISSN:	0302-9743
COBISS.SI-ID:	4292374

Secondary language

Language:	Slovenian
Title:	O problemih identifikacije v grafih in o posebnem primeru identifikacije vozlišč s pomočjo poti
Abstract:	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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back