A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph
From MaRDI portal
Publication:2032176
DOI10.1016/j.ipl.2021.106137OpenAlexW3137391013MaRDI QIDQ2032176
Publication date: 16 June 2021
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2103.04595
Cites Work
- A sensitive transitive closure algorithm
- Edge-disjoint spanning trees and depth-first search
- Improved time and space bounds for Boolean matrix multiplication
- Structure prediction and computation of sparse matrix products
- Size-estimation framework with applications to transitive closure and reachability
- Query size estimation by adaptive sampling
- The power of linear-time data reduction for maximum matching
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- A note on the complexity of computing the number of reachable vertices in a digraph
- Powers of tensors and fast matrix multiplication
- A New Combinatorial Approach for Sparse Graph Problems
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
- An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
- Parameterized Algorithms
- A transitive closure algorithm
- Depth-First Search and Linear Graph Algorithms
- Parameterized aspects of triangle enumeration
- When can graph hyperbolicity be computed in linear time?
- Parameterized complexity of diameter
- On the complexity of \(k\)-SAT
This page was built for publication: A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph
