Cut paths and their remainder structure

DOI10.1145/3790095MaRDI QIDQ7299206zbMATH OpenFDO

Authors Massimo Cairo, Shahbaz Khan, Romeo Rizzi, Sebastian M. Schmidt, Alexandru I. Tomescu, Elia C. Zirondelli

Publication date 17 July 2026

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3790095

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• 2-Edge Connectivity in Directed Graphs
• 2-vertex connectivity in directed graphs
• An optimal O(nm) algorithm for enumerating all walks common to all closed edge-covering walks of a graph
• Cut paths and their remainder structure, with applications
• Depth-First Search and Linear Graph Algorithms
• Edge-disjoint spanning trees and depth-first search
• Efficient string matching
• Finding dominators via disjoint set union
• Finding strong bridges and strong articulation points in linear time
• Genome assembly, from practice to theory: safe, complete and \textit{linear-time}
• Persistency in maximum cardinality bipartite matchings
• Safety in s-t paths, trails and walks
• Search-space reduction via essential vertices
• Simplicity in Eulerian circuits: uniqueness and safety
• Strong connectivity in directed graphs under failures, with applications
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph

This page was built for publication: Cut paths and their remainder structure

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