Component order connectivity in directed graphs

DOI10.4230/lipics.ipec.2020.2MaRDI QIDQ6068236

Jörgen Bang-Jensen, Gregory Gutin, Magnus Wahlström, Anders Yeo, Eduard Eiben

Publication date: 13 November 2023

Full work available at URL: https://arxiv.org/pdf/2007.06896

zbMATH Keywords

directed graphs; parameterized algorithms; semicomplete digraphs; component order connectivity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q27: Parameterized complexity, tractability and kernelization

Related Items

Parameterized algorithms for generalizations of directed feedback vertex set, Perfect forests in graphs and their extensions

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• On the computational complexity of vertex integrity and component order connectivity
• Graph-theoretic concepts in computer science. 15th international workshop WG '89, Castle Rolduc, The Netherlands, June 14-16, 1989. Proceedings
• Which problems have strongly exponential complexity?
• On the existence of subexponential parameterized algorithms
• Partitioning a graph into small pieces with applications to path transversal
• A fixed-parameter algorithm for the directed feedback vertex set problem
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Nondeterminism within $P^ * $
• Classes of Directed Graphs
• Almost Optimal Cover-Free Families
• Parameterized Algorithms
• Digraphs
• Parameterized algorithms for generalizations of directed feedback vertex set