On the simultaneous minimum spanning trees problem. (English) Zbl 1497.68386
Panda, B. S. (ed.) et al., Algorithms and discrete applied mathematics. 4th international conference, CALDAM 2018, Guwahati, India, February 15–17, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10743, 235-248 (2018).
Summary: Simultaneous Embedding With Fixed Edges (SEFE)
[T. Bläsius et al., “Simultaneous embedding of planar graphs”, Preprint, arXiv:1204.5853]
is a problem where given \(k\) planar graphs we ask whether they can be simultaneously embedded so that the embedding of each graph is planar and common edges are drawn the same. Problems of SEFE type have inspired questions of simultaneous geometrical representations and further derivations. Based on this motivation we investigate the generalization of the simultaneous paradigm on the classical combinatorial problem of Minimum Spanning Trees. Given \(k\) graphs with weighted edges, such that they have a common intersection, are there minimum spanning trees of the respective graphs such that they agree on the intersection? We show that the unweighted case is polynomial-time solvable while the weighted case is only polynomial-time solvable for \(k=2\) and it is \(\mathsf{NP}\)-complete for \(k\geq 3\).
For the entire collection see [Zbl 1382.68013].
For the entire collection see [Zbl 1382.68013].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. arXiv.org:1204.5853 (2015) |
| [2] | Borůvka, O., O jistém problému minimílním (About a certain minimal problem) (Czech, German summary), Práce mor. přírodověd. spol. v Brně III, 3, 37-58, 1926 · JFM 57.1343.06 |
| [3] | Jarník, V., O jistém problému minimálním, Práce Moravské Přírodovědecké Společnosti, 6, 57-63, 1930 |
| [4] | Prim, RC, Shortest connection networks and some generalizations, Bell Labs Tech. J., 36, 6, 1389-1401, 1957 · doi:10.1002/j.1538-7305.1957.tb01515.x |
| [5] | Kruskal, JB, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Am. Math. Soc., 7, 1, 48-50, 1956 · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7 |
| [6] | Graham, RL; Hell, P., On the history of the minimum spanning tree problem, Ann. Hist. Comput., 7, 1, 43-57, 1985 · Zbl 0998.68003 · doi:10.1109/MAHC.1985.10011 |
| [7] | Pettie, S.; Ramachandran, V., An optimal minimum spanning tree algorithm, J. ACM (JACM), 49, 1, 16-34, 2002 · Zbl 1323.05124 · doi:10.1145/505241.505243 |
| [8] | Karp, RM; Miller, RE; Thatcher, JW; Bohlinger, JD, Reducibility among combinatorial problems, Complexity of Computer Computations, 85-103, 1972, New York: Springer, New York · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9 |
| [9] | Edmonds, J., Submodular Functions, Matroids, and Certain Polyhedra, 68-87, 1970, New York: Gordon and Breach, New York |
| [10] | Gabow, HN; Stallmann, M.; Brauer, W., Efficient algorithms for graphic matroid intersection and parity, Automata, Languages and Programming, 210-220, 1985, Heidelberg: Springer, Heidelberg · Zbl 0567.05002 · doi:10.1007/BFb0015746 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
