Minimum perfect bipartite matchings and spanning trees under categorization
type: Item
instance of: scholarly article
title: Minimum perfect bipartite matchings and spanning trees under categorization
zbMATH Open document ID: 0776.05088
DOI: 10.1016/0166-218X(92)90165-7
author: Michael B. Richey
author: Abraham P. Punnen
published in: Discrete Applied Mathematics
publication date: 1993-01-17T00:00:00Z
review text: Let \(G=(V,E)\) be a graph with \(E\) partitioned into \(p\) categories \(S_ 1\), \(S_ 2,\dots,S_ p\), and with each edge \(e\) having a weight \(w(e)\). Let \(D\) be a set of edges a of spanning tree of \(G\) or a set of edges a of perfect bipartite matching of \(G\). It is shown: (1) The problem of finding a spanning tree or a perfect bipartite matching, for which the value of the function \[ F(D)=\max_{1\leq i\leq p}\left\{\sum_{e\in S_ i\cap D}w(e)\right\} \] is \(\leq k\), is NP- complete on bipartite outerplanar graphs iff \(p\) is fixed at \(p=2\). (2) The problem of finding a spanning tree or a perfect bipartite matching, for which the value of the function \[ f(D)=\sum^ p_{i=1}\left\{\max_{e\in S_ i\cap D}w(e)\right\} \] is \(\leq k\), is strongly NP-complete on bipartite outerplanar graphs. (3) Minimizing \(f(D)\) can be solved in polynomial time if the number of categories is fixed, but minimizing \(F(D)\) remains NP-complete.
reviewed by: M.Koman
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 97208
zbMATH Keywords: cover
zbMATH Keywords: spanning tree
zbMATH Keywords: perfect bipartite matching
zbMATH Keywords: outerplanar graphs
zbMATH Keywords: NP- complete
MaRDI profile type: Publication
cites work: Bottleneck assignment problems under categorization
cites work: Q4065051
cites work: Q4198056
cites work: Group centre and group median of a network
cites work: Minmax linear programmes with grouped variables
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Q4142699
cites work: Q4197641
cites work: On the complexity of decomposing matrices arising in satellite communication
cites work: An efficiently solvable case of the minimum weight equivalent subgraph problem
cites work: On finding spanning eulerian subgraphs
cites work: Some Generalisations of the Time Minimising Assignment Problem
cites work: Linear-time computability of combinatorial problems on series-parallel graphs
cites work: Steiner trees, partial 2–trees, and minimum IFI networks
description: scientific article; zbMATH DE number 97208