Minimum perfect bipartite matchings and spanning trees under categorization
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.
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An efficiently solvable case of the minimum weight equivalent subgraph problem
- Bottleneck assignment problems under categorization
- Group centre and group median of a network
- scientific article; zbMATH DE number 3481857 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3637614 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Linear-time computability of combinatorial problems on series-parallel graphs
- Minmax linear programmes with grouped variables
- On finding spanning eulerian subgraphs
- On the complexity of decomposing matrices arising in satellite communication
- Some Generalisations of the Time Minimising Assignment Problem
- Steiner trees, partial 2–trees, and minimum IFI networks
- Variations of the maximum leaf spanning tree problem for bipartite graphs
- Minmax combinatorial optimization
- Traveling salesman problem under categorization
- A connection between sports and matroids: how many teams can we beat?
- Ordered weighted average optimization in multiobjective spanning tree problem
- Group centre and group median of a tree
- Multiple bottleneck assignment problem
- Categorized bottleneck-minisum path problems on networks
- The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
- Maximum matchings in bipartite graphs via strong spanning trees
- The Complexity of Bottleneck Labeled Graph Problems
- A note on the hardness results for the labeled perfect matching problems in bipartite graphs
- Balanced problems on graphs with categorization of edges
- scientific article; zbMATH DE number 1786153 (Why is no real title available?)
- Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
- Generalized Bottleneck Problems∗
- The color-balanced spanning tree problem.
- The complexity of bottleneck labeled graph problems
- The biobjective minimum-cost perfect matching problem and Chinese postman problem
- On two restricted ancestors tree problems
This page was built for publication: Minimum perfect bipartite matchings and spanning trees under categorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201102)
