Minimum-maximal matching in series-parallel graphs

DOI10.1016/0377-2217(88)90258-5MaRDI QIDQ1099085zbMATH OpenOpenAlexFDO

Authors R. G. 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

matchingminimum weight subsetminimum-maximal matchingseries-parallel graphsundirected graph

Mathematics Subject Classification ID

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

Recommendations

• Decomposition algorithms for solving the minimum weight maximal matching problem
• Maximal matching polytope in trees
• Efficient algorithms for finding maximum matching in graphs
• Integer programming formulations for the minimum weighted maximal matching problem
• An optimal parallel algorithm for maximal matching

Cites work

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

Cited in

(18)

• Minimum-maximal matching in series-parallel graphs
• Algorithms for recognition of regular properties and decomposition of recursive graph families
• A graph approximation heuristic for the vertex cover problem on planar graphs
• Integer programming formulations for the minimum weighted maximal matching problem
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Minimum maximal matchings in cubic graphs
• Modelling and solving the perfect edge domination problem
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Maximum series-parallel subgraph
• Decomposition algorithms for solving the minimum weight maximal matching problem
• Maximal matching polytope in trees
• Hardness and approximation of minimum maximal matchings
• Minimum Linear Arrangement of Series-Parallel Graphs
• scientific article; zbMATH DE number 7378361 (Why is no real title available?)
• A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
• The edge versus path incidence matrix of series-parallel graphs and greedy packing
• A (1/2+1/60)-approximation algorithm for maximum weight series-parallel subgraph
• Minimum maximal matchings in phenylene chains

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

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