Planar Formulae and Their Uses
From MaRDI portal
Publication:3936195
DOI10.1137/0211025zbMath0478.68043OpenAlexW2066577300MaRDI QIDQ3936195
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211025
planar graphscombinatorial gamesNP- completenessP-space-completenessgeometric connected dominating setplanar Boolean formulaeplanar generalized geographyplanar Hamiltonian circuitplanar node cover
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (only showing first 100 items - show all)
On the dichromatic number of surfaces ⋮ A graph theoretical approach to the firebreak locating problem ⋮ Approximation algorithms for aligning points ⋮ Determining the thickness of graphs is NP-hard ⋮ On the complexity of the disjoint paths problem ⋮ It is tough to be a plumber ⋮ Approximating points by a piecewise linear function ⋮ Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues] ⋮ Positive planar satisfiability problems under 3-connectivity constraints ⋮ Complexity of circuit intersection in graphs ⋮ Satisfiability with index dependency ⋮ Plane Graphs with Parity Constraints ⋮ The computational complexity of probabilistic inference using Bayesian belief networks ⋮ Algorithmic aspects of the independent 2-rainbow domination number and independent Roman \(\{2\}\)-domination number ⋮ A Polyhedral Description of Kernels ⋮ Path cover problems with length cost ⋮ Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line ⋮ Algorithmic Aspect of Minus Domination on Small-Degree Graphs ⋮ On edge perfectness and classes of bipartite graphs ⋮ Minimum color spanning circle of imprecise points ⋮ Unnamed Item ⋮ Plane augmentation of plane graphs to meet parity constraints ⋮ The maximum independent union of cliques problem: complexity and exact approaches ⋮ Connectivity graphs of uncertainty regions ⋮ Colourful components in \(k\)-caterpillars and planar graphs ⋮ HAMILTONian circuits in chordal bipartite graphs ⋮ Distance domination in graphs with given minimum and maximum degree ⋮ Line segment covering of cells in arrangements ⋮ Restricted Power - Computational Complexity Results for Strategic Defense Games ⋮ Placing labels in road maps: algorithms and complexity ⋮ Label Placement in Road Maps ⋮ Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds ⋮ Rectangular partitions of a rectilinear polygon ⋮ The Complexity of the Partial Order Dimension Problem: Closing the Gap ⋮ Single-Player and Two-Player Buttons & Scissors Games ⋮ On the complexity of restoring corrupted colorings ⋮ A robust \(p\)-center problem under pressure to locate shelters in wildfire context ⋮ On algorithmic complexity of double Roman domination ⋮ Placing Arrows in Directed Graph Drawings ⋮ Consistent dynamic map labeling with fairness and importance ⋮ On Metric Clustering to Minimize the Sum of Radii ⋮ Unnamed Item ⋮ Minimum color spanning circle in imprecise setup ⋮ Maximizing ink in partial edge drawings of \(k\)-plane graphs ⋮ Upward and quasi-upward planarity testing of embedded mixed graphs ⋮ On caterpillar factors in graphs ⋮ Plane graphs with parity constraints ⋮ Algorithmic aspects of proportional symbol maps ⋮ The complexity of pebbling reachability and solvability in planar and outerplanar graphs ⋮ Boundary properties of the satisfiability problems ⋮ On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat} ⋮ The edge-disjoing steiner problem in graphs ⋮ GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE ⋮ Convex Quadrangulations of Bichromatic Point Sets ⋮ Identifying and Locating–Dominating Codes in (Random) Geometric Networks ⋮ EXISTENCE AND COMPUTATION OF TOURS THROUGH IMPRECISE POINTS ⋮ Hardness of \(k\)-anonymous microaggregation ⋮ A Complexity Dichotomy for the Coloring of Sparse Graphs ⋮ Sensor network topology design and analysis for efficient data gathering by a mobile mule ⋮ The inverse Voronoi problem in graphs. I: Hardness ⋮ The complexity of data aggregation in static and dynamic wireless sensor networks ⋮ Optimization for first order Delaunay triangulations ⋮ EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS ⋮ Dominating set of rectangles intersecting a straight line ⋮ Unnamed Item ⋮ The Planar k-Means Problem is NP-Hard ⋮ A Bottleneck Matching Problem with Edge-Crossing Constraints ⋮ An explicit construction of optimal dominating and [1, 2–dominating sets in grid] ⋮ Approximation algorithms for the connected sensor cover problem ⋮ The Complexity of Data Aggregation in Static and Dynamic Wireless Sensor Networks ⋮ Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems ⋮ Collaborative delivery with energy-constrained mobile robots ⋮ Extension complexity of the correlation polytope ⋮ The Monotone Satisfiability Problem with Bounded Variable Appearances ⋮ Unnamed Item ⋮ Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds ⋮ Computing the Overlaps of Two Maps ⋮ Distance Domination in Graphs ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation ⋮ Robust Self-assembly of Graphs ⋮ Minimum Eccentricity Shortest Paths in Some Structured Graph Classes ⋮ A BETTER APPROXIMATION FOR MINIMUM AVERAGE ROUTING PATH CLUSTERING PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS ⋮ On the Complexity of Clustering with Relaxed Size Constraints ⋮ Short Plane Supports for Spatial Hypergraphs ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ Radiocoloring in planar graphs: Complexity and approximations ⋮ Planar 3-SAT with a clause/variable cycle ⋮ Twin-width and polynomial kernels ⋮ Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity ⋮ On minimum- and maximum-weight minimum spanning trees with neighborhoods ⋮ On the complexity of the planar directed edge-disjoint paths problem ⋮ Discretely Following a Curve ⋮ The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects ⋮ Subdivision of the hierarchy of H-colorable graph classes by circulant graphs ⋮ Partitioning a graph into disjoint cliques and a triangle-free graph ⋮ Decision Trees for Geometric Models
This page was built for publication: Planar Formulae and Their Uses
