Perfect triangle-free 2-matchings

DOI10.1007/BFb0120901zbMath0457.05052MaRDI QIDQ3905324

William R. Pulleyblank, Cornuéjols, Gérard

Publication date: 1980

Published in: Mathematical Programming Studies (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0120901

zbMATH Keywords

Hamiltonian cycle; polynomial algorithm; perfect triangle-free 2-matching; triangle cluster

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C45: Eulerian and Hamiltonian graphs

68W99: Algorithms in computer science

Related Items

Packing $k$-Matchings and $k$-Critical Graphs, Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles, Remarks on component factors, A model for minimizing active processor time, Induced graph packing problems, Graph factors and factorization: 1985--2003: a survey, Structural properties of matroid matchings, Sufficient conditions for the existence of pseudo 2-factors without isolated vertices and small odd cycles, A fast scaling algorithm for the weighted triangle-free 2-matching problem, Solving the linear matroid parity problem as a sequence of matroid intersection problems, Applying Lehman's theorems to packing problems, 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, Dynamic matchings and quasidynamic fractional matchings. II, TRIANGLE-FREE 2-MATCHINGS REVISITED