A note on the complexity of computing the number of reachable vertices in a digraph

DOI10.1016/j.ipl.2016.05.002zbMath1362.68099arXiv1602.02129OpenAlexW2262622716MaRDI QIDQ2629773

Michele Borassi

Publication date: 7 July 2016

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityreachabilitygraph algorithmstransitive closurestrong exponential time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation ⋮ A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph

Cites Work

• Unnamed Item
• Unnamed Item
• Into the square: on the complexity of some quadratic-time solvable problems
• Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Powers of tensors and fast matrix multiplication
• A New Combinatorial Approach for Sparse Graph Problems
• The Complexity of Satisfiability of Small Depth Circuits
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Consequences of Faster Alignment of Sequences
• Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
• Fast approximation algorithms for the diameter and radius of sparse graphs
• On the complexity of \(k\)-SAT

This page was built for publication: A note on the complexity of computing the number of reachable vertices in a digraph