How to make a digraph strongly connected

DOI10.1007/BF02579270zbMath0487.05033MaRDI QIDQ1165251

András Frank

Publication date: 1981

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

strongly connected digraphminimum weight covering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items

Polyhedral proof methods in combinatorial optimization, Approximations for the maximum acyclic subgraph problem, An algorithm for minimum cost arc-connectivity orientations, Generalized polymatroids and submodular flows, An application of submodular flows, Fractional packing in ideal clutters, The ellipsoid method and its consequences in combinatorial optimization, An efficient scaling algorithm for the minimum weight bibranching problem, A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows, Robust Independence Systems, Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs, Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings, Finding feasible vectors of Edmonds-Giles polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• On two minimax theorems in graph
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• A Minimax Theorem for Directed Graphs
• An Algorithm for Submodular Functions on Graphs