The Maximum Independent Set Problem in Planar Graphs
From MaRDI portal
Publication:3599118
DOI10.1007/978-3-540-85238-4_7zbMath1173.68534OpenAlexW1587128046MaRDI QIDQ3599118
Martin Milanič, Vladimir E. Alekseev, Dmitriy S. Malyshev, Vadim V. Lozin
Publication date: 3 February 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_7
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
On integer programming with bounded determinants, Graph classes with and without powers of bounded clique-width, Weighted independent sets in a subclass of \(P_6\)-free graphs, Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs, Unnamed Item, Critical hereditary graph classes: a survey, Graphs without large apples and the maximum weight independent set problem, Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
Cites Work
- Unnamed Item
- Recent developments on graphs of bounded clique-width
- Decomposition by clique separators
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- An algorithm for finding clique cut-sets
- Computing independent sets in graphs with large girth
- A partial k-arboretum of graphs with bounded treewidth
- The four-colour theorem
- Diameter and treewidth in minor-closed graph families, revisited
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- On the vertex packing problem
- A New Algorithm for Generating All the Maximal Independent Sets
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- An upper bound on the number of cliques in a graph
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
