Minimum-maximal matching in series-parallel graphs

DOI10.1016/0377-2217(88)90258-5zbMath0637.90094OpenAlexW2040166238MaRDI QIDQ1099085

R. Gary Parker, Michael B. Richey

Publication date: 1988

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(88)90258-5

zbMATH Keywords

matchingundirected graphseries-parallel graphsminimum weight subsetminimum-maximal matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (11)

A graph approximation heuristic for the vertex cover problem on planar graphs ⋮ Minimum maximal matchings in cubic graphs ⋮ Minimum-maximal matching in series-parallel graphs ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ Hardness and approximation of minimum maximal matchings ⋮ Modelling and solving the perfect edge domination problem ⋮ Unnamed Item ⋮ Algorithms for recognition of regular properties and decomposition of recursive graph families ⋮ Integer programming formulations for the minimum weighted maximal matching problem ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ Maximal matching polytope in trees

Cites Work

• Unnamed Item
• Minimum-maximal matching in series-parallel graphs
• Parallel concepts in graph theory
• A linear algorithm for the domination number of a series-parallel graph
• Topology of series-parallel networks
• Steiner trees, partial 2–trees, and minimum IFI networks
• Steiner trees, connected domination and strongly chordal graphs
• On finding spanning eulerian subgraphs
• An efficiently solvable case of the minimum weight equivalent subgraph problem
• Edge Dominating Sets in Graphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• The biparticity of a graph
• Linear-time computation of optimal subgraphs of decomposable graphs
• Paths, Trees, and Flowers
• Decomposition of Finite Graphs Into Forests
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs

This page was built for publication: Minimum-maximal matching in series-parallel graphs