A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph
type: Item
instance of: scholarly article
title: A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph
author: Naoto Ohsaka
published in: Information Processing Letters
publication date: 2021-06-16T00:00:00Z
full work available at URL: https://arxiv.org/abs/2103.04595
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7360090
zbMATH Keywords: graph algorithms
zbMATH Keywords: reachability
zbMATH Keywords: transitive closure
zbMATH Keywords: parameterized algorithms
zbMATH Keywords: FPT in P
MaRDI profile type: Publication
OpenAlex ID: W3137391013
cites work: Size-estimation framework with applications to transitive closure and reachability
cites work: Query size estimation by adaptive sampling
cites work: Structure prediction and computation of sparse matrix products
cites work: A transitive closure algorithm
cites work: A sensitive transitive closure algorithm
cites work: A New Combinatorial Approach for Sparse Graph Problems
cites work: Improved time and space bounds for Boolean matrix multiplication
cites work: Powers of tensors and fast matrix multiplication
cites work: A note on the complexity of computing the number of reachable vertices in a digraph
cites work: On the complexity of \(k\)-SAT
cites work: Parameterized Algorithms
cites work: Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
cites work: The power of linear-time data reduction for maximum matching
cites work: An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
cites work: When can graph hyperbolicity be computed in linear time?
cites work: Parameterized aspects of triangle enumeration
cites work: Parameterized complexity of diameter
cites work: Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
cites work: Edge-disjoint spanning trees and depth-first search
cites work: Depth-First Search and Linear Graph Algorithms
DOI: 10.1016/J.IPL.2021.106137
description: scientific article; zbMATH DE number 7360090