A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs
From MaRDI portal
Publication:429657
DOI10.1016/j.disopt.2010.04.001zbMath1241.90162OpenAlexW1982316266MaRDI QIDQ429657
Publication date: 20 June 2012
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2010.04.001
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Related Items
Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles, Positive planar satisfiability problems under 3-connectivity constraints, Decomposition theorems for square-free 2-matchings in bipartite graphs, When the Gomory-chvátal closure coincides with the integer hull, Triangle-free 2-matchings and M-concave functions on jump systems, An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach, A proof of Cunningham's conjecture on restricted subgraphs and jump systems, An algorithm for finding a maximum \(t\)-matching excluding complete partite subgraphs, A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges, Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs, Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
Cites Work
- Unnamed Item
- Convexity and Steinitz's exchange property
- Combinatorial algorithms for matchings, even factors and square-free 2-factors
- Valuated matroids: A new look at the greedy algorithm
- A matching problem with side conditions
- A greedy-algorithm characterization of valuated \(\Delta\)-matroids
- Valuated matroids
- \(\Delta\)-matroids with the strong exchange conditions
- The membership problem in jump systems
- Restricted \(t\)-matchings in bipartite graphs
- Pfaffian forms and \(\Delta\)-matroids
- Matching, matroids, and extensions
- Finding maximum square-free 2-matchings in bipartite graphs
- Even factors, jump systems, and discrete convexity
- Submodular functions and optimization.
- A Weighted kt, t-Free t-Factor Algorithm for Bipartite Graphs
- On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
- Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
- Faster scaling algorithms for general graph matching problems
- Discrete Convex Analysis
- Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
- Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)
- 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