Approximation algorithms for NP-complete problems on planar graphs
From MaRDI portal
Publication:4299299
DOI10.1145/174644.174650zbMath0807.68067OpenAlexW2156760067WikidataQ55934692 ScholiaQ55934692MaRDI QIDQ4299299
Publication date: 1 March 1995
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/174644.174650
approximation schemesmaximum independent setminimum vertex coverminimum dominating setminimum edge dominating setmaximum H-matchingmaximum tile salvage
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
The longest common subsequence problem for sequences with nested arc annotations., Improving robustness of next-hop routing, Approximation algorithms for aligning points, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems, How to catch marathon cheaters: new approximation algorithms for tracking paths, Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks, A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing, An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs, Constant factor approximation for the weighted partial degree bounded edge packing problem, Triangle-free planar graphs with small independence number, On approximating (connected) 2-edge dominating set by a tree, Complexity of metric dimension on planar graphs, On approximation algorithms for the minimum satisfiability problem, Minors and dimension, Mutual exclusion scheduling, Polynomial time approximation schemes and parameterized complexity, A PTAS for the sparsest 2-spanner of 4-connected planar triangulations, Some recent progress and applications in graph minor theory, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Improved induced matchings in sparse graphs, Parallel approximation schemes for problems on planar graphs, PTAS for the minimum weighted dominating set in growth bounded graphs, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Polynomial time approximation schemes for minimum disk cover problems, Improved bounds on the planar branchwidth with respect to the largest grid minor size, New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs, Sublinear separators, fragility and subexponential expansion, A metric for rooted trees with unlabeled vertices based on nested parentheses, Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs, PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs, Interdiction problems on planar graphs, Dynamic graph-based search in unknown environments, Approximation of minimum weight spanners for sparse graphs, Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph, Linkless and flat embeddings in 3-space, A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares, An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem, Approximation algorithms via contraction decomposition, The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs, \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees, The many facets of upper domination, Complexity and lowers bounds for power edge set problem, Approximation algorithms for maximum independent set of pseudo-disks, Trimming of graphs, with application to point labeling, Shifting strategy for geometric graphs without geometry, Max NP-completeness made easy, A survey on the structure of approximation classes, Guard games on graphs: keep the intruder out!, Digraph measures: Kelly decompositions, games, and orderings, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Minimal classes of graphs of unbounded clique-width, Independent dominating set problem revisited, Greedy domination on biclique-free graphs, On triangulating \(k\)-outerplanar graphs, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Computational study on a PTAS for planar dominating set problem, Tree \(t\)-spanners in outerplanar graphs via supply demand partition, Online dominating set, Linearity of grid minors in treewidth with applications through bidimensionality, Tropical dominating sets in vertex-coloured graphs, Improved approximation algorithms for projection games, Small universal point sets for \(k\)-outerplanar graphs, On the parameterized complexity of layered graph drawing, Network pollution games, The generalized vertex cover problem and some variations, Fast minor testing in planar graphs, Local approximability of max-min and min-max linear programs, Non-cooperative facility location and covering games, Disjoint paths in sparse graphs, Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs, Approximability of clausal constraints, Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time, On some tractable and hard instances for partial incentives and target set selection, Minimum vertex cover in rectangle graphs, Complexity and approximation of the constrained forest problem, Satisfactory graph partition, variants, and generalizations, Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, On the maximum independent set problem in subclasses of subcubic graphs, Domination in graphs with bounded propagation: Algorithms, formulations and hardness results, Randomly removing \(g\) handles at once, Parameterizing above or below guaranteed values, Minor-embedding in adiabatic quantum computation. I: The parameter setting problem, Approximating the partition function of planar two-state spin systems, A simple algorithm for multicuts in planar graphs with outer terminals, A partial k-arboretum of graphs with bounded treewidth, On the approximability of the maximum agreement subtree and maximum compatible tree problems, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs, Large independent sets in random regular graphs, On the algorithmic complexity of twelve covering and independence parameters of graphs, A better constant-factor approximation for weighted dominating set in unit disk graph, Computational study on planar dominating set problem, On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering, On the complexity of reasoning about opinion diffusion under majority dynamics, Packing triangles in bounded degree graphs., Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., A 2-approximation algorithm for the minimum weight edge dominating set problem, Clustered 3-colouring graphs of bounded degree, Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation, Hitting Weighted Even Cycles in Planar Graphs, On approximation properties of the Independent set problem for degree 3 graphs, On approximating MIS over B1-VPG graphs*, On Strict (Outer-)Confluent Graphs, New Results on Directed Edge Dominating Set, Intractability of assembly sequencing: Unit disks in the plane, Inductive graph invariants and approximation algorithms, Crossing edge minimization in radial outerplanar layered graphs using segment paths, PTAS for Sparse General-valued CSPs, Splitting plane graphs to outerplanarity, Simulation of quantum many-body systems on Amazon cloud, Improved (In-)Approximability Bounds for d-Scattered Set, A fast approximation algorithm for the maximum 2-packing set problem on planar graphs, Solving cut-problems in quadratic time for graphs with bounded treewidth, NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems, Unnamed Item, Unnamed Item, Approximating sparse quadratic programs, An improved algorithm for finding maximum outerplanar subgraphs, Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs, A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS, A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs, Approximating Unique Games Using Low Diameter Graph Decomposition, Approximability of the independent feedback vertex set problem for bipartite graphs, On Approximating (Connected) 2-Edge Dominating Set by a Tree, Unnamed Item, Approximation algorithms for maximum two-dimensional pattern matching, Cost minimization in wireless networks with a bounded and unbounded number of interfaces, Unnamed Item, Optimality program in segment and string graphs, Approximating the minimum hub cover problem on planar graphs, A new lower bound for the eternal vertex cover number of graphs, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Domination in Geometric Intersection Graphs, Distributed distance-\(r\) covering problems on sparse high-girth graphs, Covering and packing of rectilinear subdivision, Distributed distance-\(r\) covering problems on sparse high-girth graphs, Approximation Algorithms for Facial Cycles in Planar Embeddings, Decomposition of Map Graphs with Applications., Unnamed Item, Introduction to the Maximum Solution Problem, Unnamed Item, Unnamed Item, Unnamed Item, Bounded clique cover of some sparse graphs, Safe Approximation and Its Relation to Kernelization, Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs, Degree-constrained decompositions of graphs: Bounded treewidth and planarity, Approximation hardness of edge dominating set problems, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, On dominating set of some subclasses of string graphs, Fixed-parameter approximation: conceptual framework and approximability results, Approximation of the Quadratic Knapsack Problem, Genus characterizes the complexity of certain graph problems: Some tight results, On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations, Conflict-Free Coloring of Graphs, Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, On graphs whose eternal vertex cover number and vertex cover number coincide, A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph, Applying clique-decomposition for computing Gromov hyperbolicity, On orthogonally guarding orthogonal polygons with bounded treewidth, Complexity of edge monitoring on some graph classes, Hardness and approximation of minimum maximal matchings, The maximum independent union of cliques problem: complexity and exact approaches, Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs, On independent set in \(B_1\)-EPG graphs, An annotated bibliography on 1-planarity, Layered separators in minor-closed graph classes with applications, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, An improved kernel for planar vertex-disjoint triangle packing, A Note on the Minimum H-Subgraph Edge Deletion, Small Point Sets for Simply-Nested Planar Graphs, Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem, Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs, Approximation Algorithms for Geometric Intersection Graphs, Complexity and Approximation Results for the Connected Vertex Cover Problem, Obtaining a Planar Graph by Vertex Deletion, Approximation algorithms for the generalized incremental knapsack problem, Non-aligned Drawings of Planar Graphs, Batch Coloring Flat Graphs and Thin, Obtaining a planar graph by vertex deletion, Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs, Sublinear-space approximation algorithms for Max \(r\)-SAT, On fractional fragility rates of graph classes, A PTAS for the Cluster Editing Problem on Planar Graphs, On strict (outer-)confluent graphs, 2-(edge-)connected edge domination number and matching number, Bounds on half graph orders in powers of sparse graphs, On Guarding Orthogonal Polygons with Sliding Cameras, Flip distance between triangulations of a planar point set is APX-hard, On approximating the \(d\)-girth of a graph, A note on the complexity of matching patterns with variables, Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs, A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees, On the hardness of range assignment problems, Algorithms for finding distance-edge-colorings of graphs, Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics, Frameworks for designing in-place graph algorithms, How to Cut a Graph into Many Pieces, Sparse covers for planar graphs and graphs that exclude a fixed minor, Packing triangles in low degree graphs and indifference graphs, Minimum vertex cover in ball graphs through local search, A 4.31-approximation for the geometric unique coverage problem on unit disks, Polynomial-time approximation schemes for piercing and covering with applications in wireless networks, An approximation of the minimum vertex cover in a graph, Independent set of intersection graphs of convex objects in 2D, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, Optimization for first order Delaunay triangulations, New tools and connections for exponential-time approximation, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Parameter testing in bounded degree graphs of subexponential growth, A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem, Layered graphs: applications and algorithms, Cost Minimisation in Multi-interface Networks, PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k, Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers, On Approximating the d-Girth of a Graph, New Results for Network Pollution Games, Distributed Dominating Set Approximations beyond Planar Graphs, ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS, Upper Domination: Complexity and Approximation, Notes on graph product structure theory, On the induced matching problem in Hamiltonian bipartite graphs, A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation, Convex dominating sets in maximal outerplanar graphs, The power of the weighted sum scalarization for approximating multiobjective optimization problems, Kernelization: New Upper and Lower Bound Techniques, Improved Induced Matchings in Sparse Graphs, The approximability of the weighted Hamiltonian path completion problem on a tree, An improved approximation bound for minimum weight dominating set on graphs of bounded arboricity, On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem, Integer plane multiflow maximisation: one-quarter-approximation and gaps, Finding, hitting and packing cycles in subexponential time on unit disk graphs, Revising Johnson's table for the 21st century, A note on approximations of directed edge dominating set, A refined search tree technique for dominating set on planar graphs, The complexity of finding harmless individuals in social networks, Parameterized computation and complexity: a new approach dealing with NP-hardness, Capacitated domination: problem complexity and approximation algorithms, Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs, On maximum independent set of categorical product and ultimate categorical ratios of graphs, Simple PTAS's for families of graphs excluding a minor, PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs
