Planar 3DM is NP-complete
From MaRDI portal
Publication:3745303
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)
Recommendations
Cited in
(64)- Perfect edge domination and efficient edge domination in graphs
- The path partition problem and related problems in bipartite graphs
- A min-max relation for stable sets in graphs with no odd-\(K_ 4\)
- scientific article; zbMATH DE number 1948176 (Why is no real title available?)
- Balanced connected graph partition
- Dual power assignment optimization and fault tolerance in WSNs
- Rikudo is NP-complete
- Complexity and approximation of the constrained forest problem
- Weighted restrained domination in subclasses of planar graphs
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- General factors of graphs
- On weighted efficient total domination
- Testing approximate symmetry in the plane is NP-hard
- Complexity, algorithmic, and computational aspects of a dial-a-ride type problem
- Approximability results for the maximum and minimum maximal induced matching problems
- Packing \([1, \Delta ]\)-factors in graphs of small degree
- Minimum total node interference in wireless sensor networks
- On protein structure alignment under distance constraint
- Some observations on holographic algorithms
- The complexity of the unit stop number problem and its implications to other related problems
- On the complexity of broadcast domination and multipacking in digraphs
- Perfect Italian domination on planar and regular graphs
- Parameterized aspects of strong subgraph closure
- On maximum \(P_3\)-packing in claw-free subcubic graphs
- Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
- Efficient sets in graphs
- Cooperative mobile guards in grids
- Better approximability results for min-max tree/cycle/path cover problems
- On the complexity of partitioning graphs into connected subgraphs
- Certain NP-complete matching problems
- The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
- Disjoint dominating and 2-dominating sets in graphs
- Swapping colored tokens on graphs
- Geometric versions of the three-dimensional assignment problem under general norms
- Weighted efficient domination problem on some perfect graphs
- Geometric three-dimensional assignment problems
- The approximability of three-dimensional assignment problems with bottleneck objective
- On the computational complexity of finding a sparse Wasserstein barycenter
- Efficient total domination in digraphs
- Total vertex-edge domination in graphs: Complexity and algorithms
- Perfect Roman domination in graphs
- Algorithmic aspects of certified domination in graphs
- Swapping Colored Tokens on Graphs
- Popular and clan-popular \(b\)-matchings
- On strongly planar 3SAT
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- The complexity of broadcasting in planar and decomposable graphs
- scientific article; zbMATH DE number 7350751 (Why is no real title available?)
- Representations of graphs and networks (coding, layouts and embeddings)
- Vertex-edge domination in cubic graphs
- Complexity of the maximum leaf spanning tree problem on planar and regular graphs
- Path puzzles: discrete tomography with a path constraint is hard
- Minimum strictly fundamental cycle bases of planar graphs are hard to find
- The complexity of broadcasting in planar and decomposable graphs
- A graph theoretical approach for the yield enhancement of reconfigurable VLSI/WSI arrays
- Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube
- Parameterizing path partitions
- On computing a center persistence diagram
- Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs
- Decomposing subcubic graphs into claws, paths or triangles
- Parameterizing path partitions
- Rectangular spiral galaxies are still hard
- Approximate separable multichoice optimization over monotone systems
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
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)
