Component order connectivity in directed graphs

DOI10.4230/lipics.ipec.2020.2OpenAlexW3116996386MaRDI 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 graphsparameterized algorithmssemicomplete digraphscomponent order connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

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

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