The Minset-Poset Approach to Representations of Graph Connectivity

DOI10.1145/2764909MaRDI QIDQ4962223zbMATH OpenOpenAlexFDO

Authors Harold N. Gabow

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2764909

zbMATH Keywords

cactus representationcode optimizationconnectivity augmentationdominatorsposets

Mathematics Subject Classification ID

Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics of partially ordered sets (06A07) Analysis of algorithms (68W40)

Recommendations

• Connectivity, graph minors, and subgraph multiplicity
• On minimum connecting transition sets in graphs
• Minimum connected dominating sets in finite graphs
• Minimum difference representations of graphs
• Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs
• On minimal neighbourhood-connected graphs
• Rank connectivity and pivot-minors of graphs
• Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
• Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
• The connectivity of minimal imperfect graphs

Cited in

(7)

• 2-vertex connectivity in directed graphs
• Minimum cuts and sparsification in hypergraphs
• Dynamic Dominators and Low-High Orders in DAGs
• On 2-strong connectivity orientations of mixed graphs and related problems
• Higher connectivity in directed graphs (invited talk)
• Faster dynamic 2-edge connectivity in directed graphs
• Minimum difference representations of graphs

This page was built for publication: The Minset-Poset Approach to Representations of Graph Connectivity

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