The Maximum Independent Set Problem in Planar Graphs
From MaRDI portal
Recommendations
- On the maximum independent set problem in subclasses of planar graphs
- Maximum independent sets in graphs of low degree
- Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
- A method of graph reduction and its applications
- scientific article; zbMATH DE number 1979518
Cites work
- A New Algorithm for Generating All the Maximal Independent Sets
- A partial k-arboretum of graphs with bounded treewidth
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- An algorithm for finding clique cut-sets
- An upper bound on the number of cliques in a graph
- Computing independent sets in graphs with large girth
- Decomposition by clique separators
- Diameter and treewidth in minor-closed graph families, revisited
- Graph minors. V. Excluding a planar graph
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Maximum independent sets in graphs of low degree
- On maximal independent sets of vertices in claw-free graphs
- On the vertex packing problem
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Recent developments on graphs of bounded clique-width
- The four-colour theorem
- The Rectilinear Steiner Tree Problem is NP-Complete
Cited in
(29)- Computational complexity of the vertex cover problem in the class of planar triangulations
- Maximum colorful independent sets in vertex-colored graphs
- Parallel approximation schemes for problems on planar graphs
- Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
- Maximum independent sets in graphs of low degree
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- Complexity of most vital nodes for independent set in graphs related to tree structures
- On the maximum independent set problem in subclasses of planar graphs
- Analysis of the influence of the number of edges on the complexity of the independent set problem
- On integer programming with bounded determinants
- An approximation algorithm for the maximum independent set problem in cubic planar graphs
- Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
- The Vertex-Disjoint Menger Problem in Planar Graphs
- Space complexity: what makes planar graphs special?
- scientific article; zbMATH DE number 867674 (Why is no real title available?)
- Critical hereditary graph classes: a survey
- Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
- Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete
- On edge-independent sets
- scientific article; zbMATH DE number 7742928 (Why is no real title available?)
- The maximal f-dependent set problem for planar graphs is in NC
- The maximal \(f\)-dependent set problem for planar graphs is in NC
- Finding proportionally dense subgraphs of maximum size in degree-constrained graphs
- On the d-independence number in 1-planar graphs
- On the independence number of 1-planar graphs
- Learning-augmented maximum independent set
- Graphs without large apples and the maximum weight independent set problem
- Graph classes with and without powers of bounded clique-width
- Weighted independent sets in a subclass of P₆-free graphs
This page was built for publication: The Maximum Independent Set Problem in Planar Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3599118)
