A fast scaling algorithm for the weighted triangle-free 2-matching problem

DOI10.1016/j.ejc.2017.07.008zbMath1373.05146OpenAlexW2756272112MaRDI QIDQ1678085

Peng Zhang

Publication date: 14 November 2017

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2017.07.008

zbMATH Keywords

polynomial algorithmperfect triangle-free 2-matchingtriangle cluster

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges

Cites Work

• Unnamed Item
• Triangle-free 2-matchings and M-concave functions on jump systems
• A matching problem with side conditions
• A data structure for dynamic trees
• Maximum skew-symmetric flows and matchings
• Clique partitions, graph compression and speeding-up algorithms
• A Fast Scaling Algorithm for the Weighted Triangle-Free 2-Matching Problem
• TRIANGLE-FREE 2-MATCHINGS REVISITED
• Perfect triangle-free 2-matchings
• Faster scaling algorithms for general graph matching problems
• Faster Scaling Algorithms for Network Problems
• Maximum matching and a polyhedron with 0,1-vertices
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: A fast scaling algorithm for the weighted triangle-free 2-matching problem