A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs

DOI10.1016/J.DISOPT.2010.04.001zbMATH Open1241.90162OpenAlexW1982316266MaRDI QIDQ429657FDOQ429657

Yusuke Kobayashi

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

Recommendations

• Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• scientific article
• Triangle-free 2-matchings revisited
• Triangle-free 2-matchings revisited

zbMATH Keywords

degree sequencesubcubic graphjump systemtriangle-free 2-matching\(M\)-concave function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Discrete Convex Analysis
• Submodular functions and optimization.
• Title not available (Why is that?)
• Faster scaling algorithms for general graph matching problems
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Valuated matroids
• A matching problem with side conditions
• The membership problem in jump systems
• Restricted \(t\)-matchings in bipartite graphs
• Matching, matroids, and extensions
• Even factors, jump systems, and discrete convexity
• Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
• 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
• A greedy-algorithm characterization of valuated \(\Delta\)-matroids
• \(\Delta\)-matroids with the strong exchange conditions
• Pfaffian forms and \(\Delta\)-matroids
• Finding maximum square-free 2-matchings in bipartite graphs
• A Weighted k_{t, t}-Free t-Factor Algorithm for Bipartite Graphs
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• Combinatorial algorithms for matchings, even factors and square-free 2-factors
• Valuated matroids: A new look at the greedy algorithm
• Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)

Cited In (15)

• 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
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• An algorithm for finding a maximum \(t\)-matching excluding complete partite subgraphs
• Positive planar satisfiability problems under 3-connectivity constraints
• A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges
• When the Gomory-chvátal closure coincides with the integer hull
• Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• Title not available (Why is that?)
• Finding triangle-free 2-factors in general graphs
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs
• Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles

This page was built for publication: A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs

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