Preserving and Increasing Local Edge-Connectivity in Mixed Graphs

DOI10.1137/S0036142993226983MaRDI QIDQ4837644zbMATH OpenFDO

Authors András Frank, Bill Jackson, Jørgen Bang-Jensen

Publication date 8 April 1996

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0036142993226983

zbMATH Keywords

digraphsedge-disjoint paths problemlocal edge- connectivitymin-max formulaemixed graphssplitting theorems

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Connectivity (05C40) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Recommendations

• Edge-splittings preserving local edge-connectivity of graphs
• Mathematical Foundations of Computer Science 2003
• Detachments Preserving Local Edge-Connectivity of Graphs
• Local-edge-connectivity in digraphs and oriented graphs
• On the minimum local-vertex-connectivity augmentation in graphs
• scientific article; zbMATH DE number 2080985
• On local connectivity of graphs
• scientific article; zbMATH DE number 6383846
• Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
• Local edge-connectivity in regular bipartite graphs

Cited in

(30)

• Covering skew-supermodular functions by hypergraphs of minimum total size
• Splitting off edges between two subsets preserving the edge-connectivity of the graph.
• Increasing digraph arc-connectivity by arc addition, reversal and complement
• A parameterized algorithmics framework for degree sequence completion problems in directed graphs
• The \((2, k)\)-connectivity augmentation problem: algorithmic aspects
• A constant-factor approximation for directed latency in quasi-polynomial time
• Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems
• On packing time-respecting arborescences
• A unifying approach to splitting-off
• The generalized terminal backup problem
• Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph
• Edge-connectivity augmentations of~graphs~and~hypergraphs
• A New Approach to Splitting-Off
• Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
• A note on mixed graphs and directed splitting off
• On packing arborescences in temporal networks
• scientific article; zbMATH DE number 842874 (Why is no real title available?)
• Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph
• New algorithms and lower bounds for all-pairs max-flow in undirected graphs
• A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
• Directed Steiner tree packing and directed tree connectivity
• An improved approximation guarantee for prize-collecting TSP
• Splitting-off in hypergraphs
• Splitting-off in hypergraphs
• A (3/2+1/e)-approximation algorithm for ordered TSP
• Graph connectivity and its augmentation: Applications of MA orderings
• A better-than-1.6-approximation for prize-collecting TSP
• A better-than-1.6-approximation for prize-collecting TSP
• Approximating prize-collecting variants of tsp
• Approximating multiple-depot capacitated vehicle routing via LP rounding

This page was built for publication: Preserving and Increasing Local Edge-Connectivity in Mixed Graphs

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