Generating 3-vertex connected spanning subgraphs

DOI10.1016/J.DISC.2007.11.067MaRDI QIDQ998366zbMATH OpenOpenAlexFDO

Authors Endre Boros, Konrad Borys, Vladimir Gurvich, Gábor Rudolf

Publication date 28 January 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.11.067

zbMATH Keywords

enumerationgenerationlisting3-vertex connected spanning subgraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Connectivity (05C40)

Recommendations

• On finding sparse three-edge-connected and three-vertex-connected spanning subgraphs
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• Publication:4763401
• ENUMERATING SPANNING AND CONNECTED SUBSETS IN GRAPHS AND MATROIDS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
• Enumerating Spanning and Connected Subsets in Graphs and Matroids

Cites work

• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• A flexible algorithm for generating all the spanning trees in undirected graphs
• Algorithms and Computation
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Dividing a Graph into Triconnected Components
• Enumerating Spanning and Connected Subsets in Graphs and Matroids
• Finding All Spanning Trees of Directed and Undirected Graphs
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Generating Minimal k-Vertex Connected Spanning Subgraphs
• Integer Programming and Combinatorial Optimization
• On enumerating all minimal solutions of feedback problems
• On generating all maximal independent sets
• The Complexity of Enumeration and Reliability Problems

Cited in

(6)

• Spanning even subgraphs of 3‐edge‐connected graphs
• ENUMERATING SPANNING AND CONNECTED SUBSETS IN GRAPHS AND MATROIDS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
• A polynomial delay algorithm for generating connected induced subgraphs of a given cardinality
• On finding sparse three-edge-connected and three-vertex-connected spanning subgraphs
• More routes for evacuation
• Enumerating Spanning and Connected Subsets in Graphs and Matroids

This page was built for publication: Generating 3-vertex connected spanning subgraphs

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