A New Connection Between Node and Edge Depth Robust Graphs

Given a directed acyclic graph (DAG) $G = (V,E)$, we say that $G$ is $(e,d)$-depth-robust (resp. $(e,d)$-edge-depth-robust) if for any set $S \subset V$ (resp. $S \subseteq E$) of at most $|S| \leq e$ nodes (resp. edges) the graph $G-S$ contains a directed path of length $d$. While edge-depth-robust...

Descrición completa

Detalles Bibliográficos

Autores principales:	Blocki, Jeremiah, Cinkoske, Mike
Formato:	Artigo
Publicado:	2019
Materias:	Data Structures and Algorithms Cryptography and Security
Acceso en liña:	https://arxiv.org/abs/1910.08920 http://arxiv.org/abs/1910.08920
Etiquetas:	Engadir etiqueta Sen Etiquetas, Sexa o primeiro en etiquetar este rexistro!