Sparse connectivity certificates via MA orderings in graphs

DOI10.1016/J.DAM.2006.04.008MaRDI QIDQ860401zbMATH OpenOpenAlexFDO

Authors Hiroshi Nagamochi

Publication date 9 January 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.04.008

zbMATH Keywords

connectivity certificatesedge-connectivitymixed cutsremovable cyclesspanning subgraphsvertex-connectivity

Mathematics Subject Classification ID

Connectivity (05C40)

Recommendations

• Graph connectivity and its augmentation: Applications of MA orderings
• Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs
• On sparse subgraphs preserving connectivity properties
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• On mixed connectivity certificates

Cites work

• \(k\)-connectivity and decomposition of graphs into forests
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A mixed version of Menger's theorem
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Grad und lokaler Zusammenhang in endlichen Graphen
• GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(<Special Issue>Network Design, Control and Optimization)
• Graph connectivity and its augmentation: Applications of MA orderings
• scientific article; zbMATH DE number 3627227 (Why is no real title available?)
• Kreuzungsfreie a,b-Wege in endlichen Graphen
• On minimally \((n,\lambda)\)-connected graphs
• On mixed connectivity certificates
• On sparse subgraphs preserving connectivity properties
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs
• Two‐connected orientations of Eulerian graphs

Cited in

(3)

• Computing vertex-disjoint paths in large graphs using MAOs
• Computing vertex-disjoint paths in large graphs using MAOs
• Graph connectivity and its augmentation: Applications of MA orderings

This page was built for publication: Sparse connectivity certificates via MA orderings in graphs

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