A note on integral generalized flows in directed partial 2-trees

DOI10.1016/j.ipl.2021.106147zbMath1478.90135OpenAlexW3169258247MaRDI QIDQ2234778

Andreas Billstein, Rainer Schrader

Publication date: 19 October 2021

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106147

zbMATH Keywords

algorithmsdirected acyclic graphpartial 2-treegeneralized series-parallelintegral generalized flows

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)

Cites Work

• Unnamed Item
• Oriented colorings of partial 2-trees
• Minimum cost flow algorithms for series-parallel networks
• An efficient parallel strategy for computing \(K\)-terminal reliability and finding most vital edges in 2-trees and partial 2-trees
• A partial k-arboretum of graphs with bounded treewidth
• Combinatorial algorithms on a class of graphs
• Generalized max flow in series-parallel graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• An O(|E|) Time Algorithm for Computing the Reliability of a Class of Directed Networks
• A Logspace Algorithm for Partial 2-Tree Canonization
• The Recognition of Series Parallel Digraphs
• Plane Embeddings of 2-Trees and Biconnected Partial 2-Trees
• Computationally Related Problems
• Algorithmic results for potential‐based flows: Easy and hard cases
• Space efficient algorithms for directed series–parallel graphs
• Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time

This page was built for publication: A note on integral generalized flows in directed partial 2-trees