On sparse subgraphs preserving connectivity properties

DOI10.1002/JGT.3190170302MaRDI QIDQ4201383zbMATH OpenOpenAlexFDO

Authors András Frank, Toshihide Ibaraki, Hiroshi Nagamochi

Publication date 24 August 1993

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.3190170302

zbMATH Keywords

connectivitysparse subgraphs

Mathematics Subject Classification ID

Connectivity (05C40)

Recommendations

• On the number of sparse connected graphs
• Sparse highly connected spanning subgraphs in dense directed graphs
• Structural Properties of Sparse Graphs
• Structural Properties of Sparse Graphs
• On the spanning connectivity of graphs
• scientific article; zbMATH DE number 4083675
• Connectivity, graph minors, and subgraph multiplicity
• Subsampling sparse graphons under minimal assumptions
• Property testing in sparse directed graphs: strong connectivity and subgraph-freeness

Cites work

• \(k\)-connectivity and decomposition of graphs into forests

Cited in

(20)

• A linear time algorithm for computing 3-edge-connected components in a multigraph
• On mixed connectivity certificates
• Minimum cost source location problem with vertex-connectivity requirements in digraphs
• Sparse graph certificates for mixed connectivity
• Implementing an efficient minimum capacity cut algorithm
• Existence of vertices of local connectivity \(k\) in digraphs of large outdegree
• Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• Approximating source location and star survivable network problems
• A note on minimizing submodular functions
• On element-connectivity preserving graph simplification
• Minimum cuts and sparsification in hypergraphs
• A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem
• Sparse highly connected spanning subgraphs in dense directed graphs
• Approximating source location and star survivable network problems
• On mixed connectivity certificates
• Space complexity of vertex connectivity oracles
• Graph connectivity and its augmentation: Applications of MA orderings
• Sparse connectivity certificates via MA orderings in graphs
• On shredders and vertex connectivity augmentation

This page was built for publication: On sparse subgraphs preserving connectivity properties

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