Planar 3DM is NP-complete
From MaRDI portal
Publication:3745303
DOI10.1016/0196-6774(86)90002-7zbMath0606.68065OpenAlexW2004759101WikidataQ56324158 ScholiaQ56324158MaRDI QIDQ3745303
Publication date: 1986
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(86)90002-7
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Complexity of the maximum leaf spanning tree problem on planar and regular graphs ⋮ Perfect edge domination and efficient edge domination in graphs ⋮ Minimum strictly fundamental cycle bases of planar graphs are hard to find ⋮ Weighted restrained domination in subclasses of planar graphs ⋮ General factors of graphs ⋮ Balanced connected graph partition ⋮ The complexity of the unit stop number problem and its implications to other related problems ⋮ Swapping Colored Tokens on Graphs ⋮ Weighted efficient domination problem on some perfect graphs ⋮ The approximability of three-dimensional assignment problems with bottleneck objective ⋮ Total vertex-edge domination in graphs: Complexity and algorithms ⋮ On strongly planar 3SAT ⋮ Cooperative mobile guards in grids ⋮ Parameterized aspects of strong subgraph closure ⋮ Approximate separable multichoice optimization over monotone systems ⋮ Unnamed Item ⋮ The complexity of broadcasting in planar and decomposable graphs ⋮ Decomposing subcubic graphs into claws, paths or triangles ⋮ Parameterizing path partitions ⋮ Rectangular spiral galaxies are still hard ⋮ Better approximability results for min-max tree/cycle/path cover problems ⋮ Complexity, algorithmic, and computational aspects of a dial-a-ride type problem ⋮ On weighted efficient total domination ⋮ The complexity of connected dominating sets and total dominating sets with specified induced subgraphs ⋮ Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube ⋮ Perfect Italian domination on planar and regular graphs ⋮ Vertex-edge domination in cubic graphs ⋮ Efficient total domination in digraphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Testing approximate symmetry in the plane is NP-hard ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Packing \([1, \Delta \)-factors in graphs of small degree] ⋮ On the complexity of broadcast domination and multipacking In digraphs ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ The path partition problem and related problems in bipartite graphs ⋮ Swapping colored tokens on graphs ⋮ Algorithmic aspects of certified domination in graphs ⋮ Geometric versions of the three-dimensional assignment problem under general norms ⋮ Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2 ⋮ Efficient sets in graphs ⋮ Popular and clan-popular \(b\)-matchings ⋮ The complexity of broadcasting in planar and decomposable graphs ⋮ Star Partitions of Perfect Graphs ⋮ Complexity and approximation of the constrained forest problem ⋮ On protein structure alignment under distance constraint ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ On the computational complexity of finding a sparse Wasserstein barycenter ⋮ A min-max relation for stable sets in graphs with no odd-\(K_ 4\) ⋮ Minimum Total Node Interference in Wireless Sensor Networks ⋮ Disjoint dominating and 2-dominating sets in graphs ⋮ Path puzzles: discrete tomography with a path constraint is hard ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph ⋮ A graph theoretical approach for the yield enhancement of reconfigurable VLSI/WSI arrays ⋮ Geometric three-dimensional assignment problems ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ Perfect Roman domination in graphs ⋮ On the complexity of partitioning graphs into connected subgraphs ⋮ Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs ⋮ Dual power assignment optimization and fault tolerance in WSNs ⋮ Rikudo is NP-complete
