Independence free graphs and vertex connectivity augmentation

DOI10.1016/j.jctb.2004.01.004zbMath1059.05064OpenAlexW2116510876MaRDI QIDQ1775893

Tibor Jordán, Bill Jackson

Publication date: 4 May 2005

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2004.01.004

zbMATH Keywords

AlgorithmsConnectivity of graphsVertex-connectivity augmentation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (21)

Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ BOUNDED LENGTH, 2-EDGE AUGMENTATION OF GEOMETRIC PLANAR GRAPHS ⋮ On triconnected and cubic plane graphs on given point sets ⋮ Augmenting the connectivity of outerplanar graphs ⋮ Structured Connectivity Augmentation ⋮ Structured Connectivity Augmentation ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Property testing on \(k\)-vertex-connectivity of graphs ⋮ Approximating node-connectivity augmentation problems ⋮ Augmenting the edge connectivity of planar straight line graphs to three ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Augmenting the connectivity of geometric graphs ⋮ Tight approximation algorithm for connectivity augmentation problems ⋮ Connectivity augmentation in planar straight line graphs ⋮ Approximating k-Connected m-Dominating Sets ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Local edge-connectivity augmentation in hypergraphs is NP-complete ⋮ The \((2, k)\)-connectivity augmentation problem: algorithmic aspects ⋮ Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\)

Cites Work

• Unnamed Item
• Unnamed Item
• Edge-connectivity augmentation problems
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A minimum 3-connectivity augmentation of a graph
• How to make a graph four-connected
• On the complexity of recognizing tough graphs
• A note on the vertex-connectivity augmentation problem
• Non-separable detachments of graphs
• On the optimal vertex-connectivity augmentation
• Minimal edge-coverings of pairs of sets
• Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
• The minimum augmentation of any graph to aK-edge-connected graph
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• Augmentation Problems
• Extremal graphs in connectivity augmentation
• On Four-Connecting a Triconnected Graph
• Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation

This page was built for publication: Independence free graphs and vertex connectivity augmentation