Safety in s-t paths, trails and walks

DOI10.1007/S00453-021-00877-WMaRDI QIDQ2118205zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph algorithmdirected graphsafetygenome assemblyconnectivity problemstrong articulation pointstrong bridge

Mathematics Subject Classification ID

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

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

Cites work

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

Describes a project that uses

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)