An algorithm for (n-3)-connectivity augmentation problem: jump system approach
From MaRDI portal
Publication:414633
DOI10.1016/J.JCTB.2011.08.007zbMATH Open1241.05061OpenAlexW2148517677MaRDI QIDQ414633FDOQ414633
Authors: Kristóf Bérczi, Yusuke Kobayashi 
Publication date: 11 May 2012
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.2011.08.007
Recommendations
Cites Work
- Discrete Convex Analysis
- Submodular functions and optimization.
- Title not available (Why is that?)
- Faster scaling algorithms for general graph matching problems
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- Some simplified NP-complete graph problems
- Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
- A Short Proof of the Factor Theorem for Finite Graphs
- Augmenting undirected node-connectivity by one
- Finding a Smallest Augmentation to Biconnect a Graph
- Augmentation Problems
- Valuated matroids
- A matching problem with side conditions
- The membership problem in jump systems
- Restricted \(t\)-matchings in bipartite graphs
- Matching, matroids, and extensions
- On the optimal vertex-connectivity augmentation
- Minimal edge-coverings of pairs of sets
- Even factors, jump systems, and discrete convexity
- Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
- A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs
- Operations on M‐Convex Functions on Jump Systems
- M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
- Integer Programming and Combinatorial Optimization
- Convexity and Steinitz's exchange property
- An approximation algorithm for minimum-cost vertex-connectivity problems
- A greedy-algorithm characterization of valuated \(\Delta\)-matroids
- Directed vertex-connectivity augmentation
- \(\Delta\)-matroids with the strong exchange conditions
- A note on the vertex-connectivity augmentation problem
- Independence free graphs and vertex connectivity augmentation
- Pfaffian forms and \(\Delta\)-matroids
- A smallest augmentation to 3-connect a graph
- Maximum skew-symmetric flows and matchings
- Finding maximum square-free 2-matchings in bipartite graphs
- Title not available (Why is that?)
- Primal-dual approach for directed vertex connectivity augmentation and generalizations
- A weighted \(K_{t,t}\)-free \(t\)-factor algorithm for bipartite graphs
- On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
- Title not available (Why is that?)
- On Four-Connecting a Triconnected Graph
- A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
- Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation (extended abstract)
- Combinatorial algorithms for matchings, even factors and square-free 2-factors
- Valuated matroids: A new look at the greedy algorithm
- On shredders and vertex connectivity augmentation
Cited In (14)
- Triangle-free 2-matchings and M-concave functions on jump systems
- A proof of Cunningham's conjecture on restricted subgraphs and jump systems
- A note on M-convex functions on jump systems
- Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
- Decomposition theorems for square-free 2-matchings in bipartite graphs
- A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges
- Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
- Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids
- Decomposition theorems for square-free 2-matchings in bipartite graphs
- On basic operations related to network induction of discrete convex functions
- Two disjoint shortest paths problem with non-negative edge length
- Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids
- Finding triangle-free 2-factors in general graphs
- A survey of fundamental operations on discrete convex functions of various kinds
This page was built for publication: An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414633)
