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

DOI10.1016/J.IPL.2021.106147MaRDI QIDQ2234778zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 6861995
• Analysis on trees with nondoubling flow measures
• A note on generalized flows
• A generalization of 0-sum flows in graphs
• A note on multiflows and treewidth
• scientific article; zbMATH DE number 910923
• Nowhere-zero integral chains and flows in bidirected graphs
• The lattice of integral flows and the lattice of integral cuts on a finite graph
• The flow space of a directed \(G\)-graph
• Integrality properties of edge path tree families

Cites work

• scientific article; zbMATH DE number 840702 (Why is no real title available?)
• A Logspace Algorithm for Partial 2-Tree Canonization
• A partial k-arboretum of graphs with bounded treewidth
• Algorithmic results for potential‐based flows: Easy and hard cases
• An O(|E|) Time Algorithm for Computing the Reliability of a Class of Directed Networks
• An efficient parallel strategy for computing \(K\)-terminal reliability and finding most vital edges in 2-trees and partial 2-trees
• Combinatorial algorithms on a class of graphs
• Computationally Related Problems
• Computing minimum cycle bases in weighted partial 2-trees in linear time
• Generalized max flow in series-parallel graphs
• Minimum cost flow algorithms for series-parallel networks
• Oriented colorings of partial 2-trees
• Plane Embeddings of 2-Trees and Biconnected Partial 2-Trees
• Space efficient algorithms for directed series–parallel graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• The Recognition of Series Parallel Digraphs

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

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