On the maximum independent set problem in subclasses of planar graphs

DOI10.7155/JGAA.00207MaRDI QIDQ3075609zbMATH OpenOpenAlexFDO

Authors Martin Milanič, Vadim Lozin

Publication date 16 February 2011

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00207

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Maximum Independent Set Problem in Planar Graphs
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• On the maximum independent set problem in subclasses of subcubic graphs

Cited in

(25)

• A method of graph reduction and its applications
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• New potential functions for greedy independence and coloring
• Layered graphs: applications and algorithms
• New sufficient conditions for \(\alpha\)-redundant vertices
• The maximum independent set problem in subclasses of subcubic graphs
• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• Remarks on the complexity of signed k-independence on graphs.
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• The Maximum Independent Set Problem in Planar Graphs
• An approximation algorithm for the maximum independent set problem in cubic planar graphs
• Vertex-transitive CIS graphs
• On minimum maximal distance-\(k\) matchings
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• 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
• The maximal f-dependent set problem for planar graphs is in NC
• The maximal \(f\)-dependent set problem for planar graphs is in NC
• On the d-independence number in 1-planar graphs
• On the independence number of 1-planar graphs
• Partitioning vertices of graphs into paths of the same length
• Minimizing maximum dissatisfaction in the allocation of indivisible items under a common preference graph
• On the maximum independent set problem in graphs of bounded maximum degree

This page was built for publication: On the maximum independent set problem in subclasses of planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3075609)