Minimum perfect bipartite matchings and spanning trees under categorization

DOI10.1016/0166-218X(92)90165-7zbMath0776.05088MaRDI QIDQ1201102

Abraham P. Punnen, Michael B. Richey

Publication date: 17 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

spanning treeouterplanar graphscoverNP- completeperfect bipartite matching

Mathematics Subject Classification ID

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

Related Items (15)

Categorized bottleneck-minisum path problems on networks ⋮ Minmax combinatorial optimization ⋮ The Complexity of Bottleneck Labeled Graph Problems ⋮ Generalized Bottleneck Problems^∗ ⋮ A connection between sports and matroids: how many teams can we beat? ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ Ordered weighted average optimization in multiobjective spanning tree problem ⋮ Traveling salesman problem under categorization ⋮ A note on the hardness results for the labeled perfect matching problems in bipartite graphs ⋮ The complexity of bottleneck labeled graph problems ⋮ Group centre and group median of a tree ⋮ Multiple bottleneck assignment problem ⋮ Unnamed Item ⋮ On two restricted ancestors tree problems ⋮ The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of decomposing matrices arising in satellite communication
• Minmax linear programmes with grouped variables
• Group centre and group median of a network
• Bottleneck assignment problems under categorization
• Steiner trees, partial 2–trees, and minimum IFI networks
• On finding spanning eulerian subgraphs
• An efficiently solvable case of the minimum weight equivalent subgraph problem
• Some Generalisations of the Time Minimising Assignment Problem
• Linear-time computability of combinatorial problems on series-parallel graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Minimum perfect bipartite matchings and spanning trees under categorization