Safety in s-t paths, trails and walks

DOI10.1007/S00453-021-00877-WOpenAlexW3207959194MaRDI QIDQ2118205FDOQ2118205

Authors: Massimo Cairo, Shahbaz Khan, Romeo Rizzi, Alexandru I. Tomescu, Sebastian M. Schmidt 

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00877-w

Recommendations

• A simplified algorithm computing all \(s\)-\(t\) bridges and articulation points
• Finding strong bridges and strong articulation points in linear time
• Finding paths with minimum shared edges
• Finding paths with minimum shared edges
• Safe sets in graphs: graph classes and structural parameters

zbMATH Keywords

graph algorithmdirected graphsafetygenome assemblyconnectivity problemstrong articulation pointstrong bridge

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• The algorithm design manual
• Maximal Flow Through a Network
• Graph theory
• Introduction to algorithms.
• Blockers and transversals
• The directed subgraph homeomorphism problem
• Persistency in maximum cardinality bipartite matchings
• A note on finding the bridges of a graph
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Dominators in Linear Time
• Finding strong bridges and strong articulation points in linear time
• A linear-time algorithm for a special case of disjoint set union
• Edge-disjoint spanning trees and depth-first search
• Handbook of graph theory
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph
• Persistency in the assignment and transportation problems
• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
• A simplified algorithm computing all \(s\)-\(t\) bridges and articulation points
• Safe and complete contig assembly via omnitigs
• An optimal \(O(nm)\) algorithm for enumerating all walks common to all closed edge-covering walks of a graph

Cited In (2)

• Safety and completeness in flow decompositions for RNA assembly
• A simplified algorithm computing all \(s\)-\(t\) bridges and articulation points

Uses Software

• Stony Brook

This page was built for publication: Safety in \(s\)-\(t\) paths, trails and walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118205)