Cover Image

Linear-Time Safe-Alternating DFS and SCCs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Comin, Carlo, Rizzi, Romeo
Format:	Preprint
Published:	2016
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the power of standard DFS and BFS
by: Bui-Xuan, Binh-Minh, et al.
Published: (2026)

Engineering Semi-streaming DFS algorithms
by: Bhagavan, Kancharla Nikhilesh, et al.
Published: (2024)

Safe Sequences via Dominators in DAGs for Path-Covering Problems
by: Sena, Francisco, et al.
Published: (2024)

Solving the Probabilistic Profitable Tour Problem on a Tree
by: Angelelli, Enrico, et al.
Published: (2022)

A novel DFS/BFS approach towards link prediction
by: Dörpinghaus, Jens, et al.
Published: (2024)

Generalizing Roberts' characterization of unit interval graphs
by: Martínez, Virginia Ardévol, et al.
Published: (2024)

Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework
by: Sena, Francisco, et al.
Published: (2026)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Deterministic Mincut in Almost-Linear Time
by: Li, Jason
Published: (2021)

Parameterized Linear Time Transitive Closure
by: Kritikakis, Giorgos, et al.
Published: (2024)

Approximating Partition in Near-Linear Time
by: Chen, Lin, et al.
Published: (2024)

Verifying Shortest Paths in Linear Time
by: Shokry, Ahmed, et al.
Published: (2024)

On Solving Linear Systems in Sublinear Time
by: Andoni, Alexandr, et al.
Published: (2018)

Network Unreliability in Almost-Linear Time
by: Cen, Ruoxu, et al.
Published: (2025)

Unbreakable Decomposition in Close-to-Linear Time
by: Anand, Aditya, et al.
Published: (2024)

Approximating Directed Connectivity in Almost-Linear Time
by: Quanrud, Kent
Published: (2025)

Improved Tree Sparsifiers in Near-Linear Time
by: Agassy, Daniel, et al.
Published: (2025)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Deterministic Almost-Linear-Time Gomory-Hu Trees
by: Abboud, Amir, et al.
Published: (2025)

Separator Theorem for Minor-Free Graphs in Linear Time
by: Bonnet, Édouard, et al.
Published: (2025)

Bellman-Ford in Almost-Linear Time for Dense Graphs
by: Li, George Z., et al.
Published: (2026)

Solving Hypergraph Laplacian Systems in Almost-Linear Time
by: Yoshida, Yuichi
Published: (2026)

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
by: Henzinger, Monika, et al.
Published: (2025)

Linear-Time Multilevel Graph Partitioning via Edge Sparsification
by: Gottesbüren, Lars, et al.
Published: (2025)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
by: Buchem, Moritz, et al.
Published: (2024)

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
by: Kwok, Tsz Chiu, et al.
Published: (2025)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

Split Algorithm in Linear Time for the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time Windows
by: Gibbons, Ethan, et al.
Published: (2026)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
by: Elkin, Michael, et al.
Published: (2024)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Mömke, Tobias, et al.
Published: (2024)

A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs
by: Alejandro-Soto, J. A., et al.
Published: (2025)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
by: Bucić, Matija, et al.
Published: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
by: Haeupler, Bernhard, et al.
Published: (2025)

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
by: Harada, Kaito, et al.
Published: (2024)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
by: Hua, Kevin, et al.
Published: (2024)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
by: Brand, Jan van den, et al.
Published: (2024)

Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
by: Liu, Yang P.
Published: (2025)

Numerical Linear Algebra in Linear Space
by: Liu, Yiping, et al.
Published: (2025)