Sparse connectivity certificates via MA orderings in graphs

DOI10.1016/j.dam.2006.04.008zbMath1129.05025OpenAlexW2080725679MaRDI QIDQ860401

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

spanning subgraphsedge-connectivityvertex-connectivityconnectivity certificatesmixed cutsremovable cycles

Mathematics Subject Classification ID

Connectivity (05C40)

Related Items (2)

Unnamed Item ⋮ Computing vertex-disjoint paths in large graphs using MAOs

Cites Work

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

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