Component order connectivity in directed graphs

DOI10.1007/s00453-022-01004-zMaRDI QIDQ2165039

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

Publication date: 18 August 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

directed graph; strong connectivity; parameterized complexity; order connectivity

Mathematics Subject Classification ID

68Wxx: Algorithms in computer science

05Cxx: Graph theory

Related Items

A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• On the computational complexity of vertex integrity and component order connectivity
• Which problems have strongly exponential complexity?
• On the existence of subexponential parameterized algorithms
• Partitioning a graph into small pieces with applications to path transversal
• Parametrized complexity theory.
• 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