Planar 3DM is NP-complete
From MaRDI portal
Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cited in
(71)- On the complexity of partitioning graphs into connected subgraphs
- General factors of graphs
- Representations of graphs and networks (coding, layouts and embeddings)
- Testing approximate symmetry in the plane is NP-hard
- 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
- Weighted efficient domination problem on some perfect graphs
- The complexity of broadcasting in planar and decomposable graphs
- Perfect edge domination and efficient edge domination in graphs
- Some observations on holographic algorithms
- Swapping colored tokens on graphs
- Geometric versions of the three-dimensional assignment problem under general norms
- The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
- On the complexity of broadcast domination and multipacking in digraphs
- On maximum \(P_3\)-packing in claw-free subcubic graphs
- On the computational complexity of finding a sparse Wasserstein barycenter
- Rikudo is NP-complete
- The complexity of the unit stop number problem and its implications to other related problems
- Parameterized aspects of strong subgraph closure
- Perfect Italian domination on planar and regular graphs
- Vertex-edge domination in cubic graphs
- Popular and clan-popular b-matchings
- Disjoint dominating and 2-dominating sets in graphs
- Path puzzles: discrete tomography with a path constraint is hard
- Perfect Roman domination in graphs
- Dual power assignment optimization and fault tolerance in WSNs
- Better approximability results for min-max tree/cycle/path cover problems
- Packing \([1, \Delta ]\)-factors in graphs of small degree
- The path partition problem and related problems in bipartite graphs
- Complexity of the maximum leaf spanning tree problem on planar and regular graphs
- Minimum strictly fundamental cycle bases of planar graphs are hard to find
- Approximate separable multichoice optimization over monotone systems
- Rectangular spiral galaxies are still hard
- Weighted restrained domination in subclasses of planar graphs
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- Minimum total node interference in wireless sensor networks
- On strongly planar 3SAT
- Swapping Colored Tokens on Graphs
- On weighted efficient total domination
- scientific article; zbMATH DE number 1948176 (Why is no real title available?)
- Efficient total domination in digraphs
- scientific article; zbMATH DE number 7350751 (Why is no real title available?)
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- Total vertex-edge domination in graphs: Complexity and algorithms
- Complexity and approximation of the constrained forest problem
- On protein structure alignment under distance constraint
- A min-max relation for stable sets in graphs with no odd-\(K_ 4\)
- Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs
- Decomposing subcubic graphs into claws, paths or triangles
- Parameterizing path partitions
- Algorithmic aspects of certified domination in graphs
- Complexity, algorithmic, and computational aspects of a dial-a-ride type problem
- Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube
- The complexity of broadcasting in planar and decomposable graphs
- On computing a center persistence diagram
- Parameterizing path partitions
- Linear planar 3-SAT
- The d-distance p-packing domination number: complexity, cycles, and trees
- Cluster vertex deletion problems on cubic graphs
- Hardness of pre-assignment problem for unique minimum vertex cover on planar graphs with maximum degree 3
- Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
- Efficient sets in graphs
- Partitioning vertices of graphs into paths of the same length
- Chromatic cost coloring of weighted bipartite graphs
- Shortest longest-path graph orientations
- Certain NP-complete matching problems
- Balanced connected graph partition
- The approximability of three-dimensional assignment problems with bottleneck objective
- Cooperative mobile guards in grids
- Approximability results for the maximum and minimum maximal induced matching problems
This page was built for publication: Planar 3DM is NP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3745303)
