Premium
On persistent directed graphs
Author(s) -
BangJensen Jorgen,
Jordán Tibor
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20248
Subject(s) - combinatorics , directed graph , directed acyclic graph , persistence (discontinuity) , mathematics , discrete mathematics , longest path problem , vertex (graph theory) , time complexity , chordal graph , polynomial , graph , geotechnical engineering , engineering , mathematical analysis
The concept of persistent directed graphs was introduced by Hendrickx et al. to help analyze the stability of autonomous agent systems. They provided a combinatorial characterization for persistence but the complexity of testing persistence remained open. In this note we show that for directed graphs D with ∑ v ε V ( D ) min{ δ D ( v ), 2} ≤ 2∣ V ( D )∣ − 3 persistence can be tested in polynomial time, where δ D ( v ) denotes the out‐degree of vertex v in D . This family of directed graphs includes acyclic digraphs (for which an efficient algorithm was known) as well as all digraphs with a leader‐follower structure. We also discuss some related orientation problems. Among others we point out that the existence of an acyclic persistent orientation can be tested in polynomial time for all graphs. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008