An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
type: Item
instance of: scholarly article
title: An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
zbMATH Open document ID: 1241.05061
author: Kristóf Bérczi
author: Yusuke Kobayashi
published in: Journal of Combinatorial Theory. Series B
publication date: 2012-05-11T00:00:00Z
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 6033273
zbMATH Keywords: connectivity augmentation
zbMATH Keywords: square-free 2-matching
zbMATH Keywords: jump system
zbMATH Keywords: subcubic graph
MaRDI profile type: Publication
full work available at URL: j.jctb.2011.08.007
OpenAlex ID: W2148517677
cites work: Integer Programming and Combinatorial Optimization
cites work: A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
cites work: Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
cites work: A matching problem with side conditions
cites work: Matching, matroids, and extensions
cites work: A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
cites work: Valuated matroids: A new look at the greedy algorithm
cites work: A greedy-algorithm characterization of valuated \(\Delta\)-matroids
cites work: Valuated matroids
cites work: Augmentation Problems
cites work: Restricted \(t\)-matchings in bipartite graphs
cites work: Minimal edge-coverings of pairs of sets
cites work: Directed vertex-connectivity augmentation
cites work: Submodular functions and optimization.
cites work: Q3138921
cites work: Faster scaling algorithms for general graph matching problems
cites work: Some simplified NP-complete graph problems
cites work: Maximum skew-symmetric flows and matchings
cites work: Finding maximum square-free 2-matchings in bipartite graphs
cites work: On Four-Connecting a Triconnected Graph
cites work: Finding a Smallest Augmentation to Biconnect a Graph
cites work: Q2721988
cites work: Q4472504
cites work: Independence free graphs and vertex connectivity augmentation
cites work: On the optimal vertex-connectivity augmentation
cites work: A note on the vertex-connectivity augmentation problem
cites work: A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs
cites work: Operations on M‐Convex Functions on Jump Systems
cites work: Even factors, jump systems, and discrete convexity
cites work: On shredders and vertex connectivity augmentation
cites work: The membership problem in jump systems
cites work: On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
cites work: Convexity and Steinitz's exchange property
cites work: Discrete Convex Analysis
cites work: M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
cites work: Combinatorial algorithms for matchings, even factors and square-free 2-factors
cites work: An approximation algorithm for minimum-cost vertex-connectivity problems
cites work: Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
cites work: A Weighted kt, t-Free t-Factor Algorithm for Bipartite Graphs
cites work: A Short Proof of the Factor Theorem for Finite Graphs
cites work: Augmenting undirected node-connectivity by one
cites work: Primal-dual approach for directed vertex connectivity augmentation and generalizations
cites work: A smallest augmentation to 3-connect a graph
cites work: Pfaffian forms and \(\Delta\)-matroids
cites work: \(\Delta\)-matroids with the strong exchange conditions
cites work: Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation (extended abstract)
DOI: 10.1016/J.JCTB.2011.08.007
description: scientific article; zbMATH DE number 6033273