Approximation algorithms for NP-complete problems on planar graphs

DOI10.1145/174644.174650zbMath0807.68067DBLPjournals/jacm/Baker94OpenAlexW2156760067WikidataQ55934692 ScholiaQ55934692MaRDI QIDQ4299299

Brenda S. Baker

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

zbMATH Keywords

approximation schemesmaximum independent setminimum vertex coverminimum dominating setminimum edge dominating setmaximum H-matchingmaximum tile salvage

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (only showing first 100 items - show all)

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

This page was built for publication: Approximation algorithms for NP-complete problems on planar graphs