Parameterized complexity of the maximum independent set problem and the speed of hereditary properties

DOI10.1016/j.endm.2009.07.021zbMath1273.68183OpenAlexW2068456641MaRDI QIDQ2851451

Vadim V. Lozin

Publication date: 10 October 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.07.021

zbMATH Keywords

Ramsey theoryhereditary propertiesparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number ⋮ Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes

Cites Work

• Unnamed Item
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• The speed of hereditary properties of graphs
• Parametrized complexity theory.
• Proper minor-closed families are small
• Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
• On graphs with polynomially solvable maximum-weight clique problem
• A New Algorithm for Generating All the Maximal Independent Sets
• Triangles, 4-Cycles and Parameterized (In-)Tractability

This page was built for publication: Parameterized complexity of the maximum independent set problem and the speed of hereditary properties