Maximum independent sets in subcubic graphs: New results
Copyright policy )Maximum independent sets in subcubic graphs: New results
The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We present a polynomial-time solution in a subclass of subcubic graphs generalizing several previously known results.
- French National Centre for Scientific Research France
- PSL Research University France
- Linguistics University of Nizhny Novgorod Russian Federation
- Paris Dauphine University France
- University of Warwick United Kingdom
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Analysis of algorithms and problem complexity, Polynomial algorithm, subcubic graph, polynomial algorithm, 003, 004, maximum independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Subcubic graph, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Maximum independent set, QA, Recherche opérationnelle, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Analysis of algorithms and problem complexity, Polynomial algorithm, subcubic graph, polynomial algorithm, 003, 004, maximum independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Subcubic graph, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Maximum independent set, QA, Recherche opérationnelle, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).2 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!