arrow
返回

Separating path systems in trees

delete2025-12-27
delete0
PRE
AI
F
Francisco Arrepol
P
Patricio Asenjo
R
Raúl Astete
V
Victor Cartes
A
Anahí Gajardo
V
Valeria Henríquez
C
Catalina Opazo
N
Nicolás Sanhueza‐Matamala
C
Christopher Thraves *
DOI:10.1007/s10957-025-02894-zdelete
delete原文链接
delete分享
delete收藏
摘要

摘要

En 中文
对于图G,G的边分离(resp. 顶点分离)路径系统是一个路径族,使得对于G中的任意一对边e1,e2(resp. 任意一对顶点v1,v2),族中至少存在一条路径包含e1或e2(resp. v1或v2)但不同时包含两者。我们确定了任意树T的最小边分离路径系统的大小,将其表示为其叶节点数和度为二的顶点数的函数。我们得到了树的最小顶点分离路径系统大小的界,并证明在许多情况下这些界是紧的。对于定义的一种变体,即要求路径系统同时分离边和顶点,我们也得到了类似的结果。最后,我们研究了Erdős-Rényi随机图中最小顶点分离路径系统的大小。
Keyword:
Separating path systems
Separating families
Identifying families
Trees

期刊

J
Journal of Optimization Theory and Applications
IF:
1.5
论文数:
184
被引数:
8.2K

机构

U
Universidad de Concepción
学者数:
266
论文数: 110
被引数: 2.8K
引用论文

引用论文

Approximation algorithms for the test cover problem
err2003-09-01
err0
PREAI
errK.M.J. De Bontridder; B.V. Halld�rsson; M.M. Halld�rsson; C.A.J. Hurkens; J.K. Lenstra; R. Ravi; L. Stougie
err分享
err收藏
Separating the edges of a graph by a linear number of paths
err
err0
PREAI
errBonamy,Marthe; Botler,Fábio; Dross,François; Naia,Tássio; Skokan,Jozef
err分享
err收藏
Identifying path covers in graphs
err2013-11-01
err0
PREAI
errFoucaud,Florent; Kovše,Matjaž
err分享
err收藏
err分享
err收藏
On the path separation number of graphs
err2016-11-01
err0
PREAI
errBalogh,József; Csaba,Béla; Martin,Ryan R.; Pluhár,András
err分享
err收藏
err分享
err收藏
没有更多内容