Approximation algorithms for NP-complete problems on planar graphs
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 220337
- Approximation algorithms for graph approximation problems
- Parallel approximation schemes for problems on planar graphs
- Linear-time algorithms for problems on planar graphs with fixed disk dimension
- Planar graphs: Theory and algorithms
- STACS 2004
- Fast sub-exponential algorithms and compactness in planar graphs
- A Better Approximation Algorithm for Finding Planar Subgraphs
- scientific article; zbMATH DE number 871895
- Coverability and sub-exponential parameterized algorithms in planar graphs
Cited in
(only showing first 100 items - show all)- Parameterizing above or below guaranteed values
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- A simple algorithm for multicuts in planar graphs with outer terminals
- On the approximability of the maximum agreement subtree and maximum compatible tree problems
- Large independent sets in random regular graphs
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Computational study on planar dominating set problem
- A partial k-arboretum of graphs with bounded treewidth
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- On approximation algorithms for the minimum satisfiability problem
- Mutual exclusion scheduling
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- A (3+)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
- Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph
- The many facets of upper domination
- Complexity and lowers bounds for power edge set problem
- Greedy domination on biclique-free graphs
- Computational study on a PTAS for planar dominating set problem
- Online dominating set
- Network pollution games
- The generalized vertex cover problem and some variations
- Fast minor testing in planar graphs
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Packing triangles in bounded degree graphs.
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- The longest common subsequence problem for sequences with nested arc annotations.
- Approximation algorithms for aligning points
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Parallel approximation schemes for problems on planar graphs
- PTAS for the minimum weighted dominating set in growth bounded graphs
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- 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
- Trimming of graphs, with application to point labeling
- Max NP-completeness made easy
- Small universal point sets for \(k\)-outerplanar graphs
- On some tractable and hard instances for partial incentives and target set selection
- 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
- Notes on graph product structure theory
- On the induced matching problem in Hamiltonian bipartite graphs
- The power of the weighted sum scalarization for approximating multiobjective optimization problems
- 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
- Revising Johnson's table for the 21st century
- A note on approximations of directed edge dominating set
- On dominating set of some subclasses of string 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
- Complexity of edge monitoring on some graph classes
- The maximum independent union of cliques problem: complexity and exact approaches
- On independent set in \(B_1\)-EPG graphs
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- On fractional fragility rates of graph classes
- On strict (outer-)confluent graphs
- A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
- Frameworks for designing in-place graph algorithms
- Sparse covers for planar graphs and graphs that exclude a fixed minor
- Minimum vertex cover in ball graphs through local search
- A 4.31-approximation for the geometric unique coverage problem on unit disks
- An approximation of the minimum vertex cover in a graph
- 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
- Layered graphs: applications and algorithms
- Convex dominating sets in maximal outerplanar graphs
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- The complexity of finding harmless individuals in social networks
- Capacitated domination: problem complexity and approximation algorithms
- 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
- Bounded clique cover of some sparse graphs
- Degree-constrained decompositions of graphs: Bounded treewidth and planarity
- Approximation hardness of edge dominating set problems
- Fixed-parameter approximation: conceptual framework and approximability results
- Applying clique-decomposition for computing Gromov hyperbolicity
- An annotated bibliography on 1-planarity
- Layered separators in minor-closed graph classes with applications
- Obtaining a planar graph by vertex deletion
- 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
- Algorithms for finding distance-edge-colorings of graphs
- Packing triangles in low degree graphs and indifference graphs
- Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
- Independent set of intersection graphs of convex objects in 2D
- The approximability of the weighted Hamiltonian path completion problem on a tree
- A refined search tree technique for dominating set on planar graphs
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Genus characterizes the complexity of certain graph problems: Some tight results
- On orthogonally guarding orthogonal polygons with bounded treewidth
- Improving robustness of next-hop routing
- Kernelization and approximation of distance-r independent sets on nowhere dense graphs
This page was built for publication: Approximation algorithms for NP-complete problems on planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4299299)
