Combining decomposition approaches for the maximum weight stable set problem

DOI10.1016/j.tcs.2023.113914OpenAlexW4367056879MaRDI QIDQ6040632

Andreas Brandstädt, Raffaele Mosca

Publication date: 19 May 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113914

zbMATH Keywords

polynomial time algorithmgraph algorithmsmaximum weight independent set problemdecomposition by clique separatorsdecomposition by anti-neighborhood of verticesdecomposition by homogeneous sets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Graphs without large apples and the maximum weight independent set problem
• Maximum weight independent sets in hole- and co-chair-free graphs
• On independent vertex sets in subclasses of apple-free graphs
• Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
• Decomposition by clique separators
• Polytope des independants d'un graphe série-parallèle
• An algorithm for finding clique cut-sets
• Algorithms on clique separable graphs
• Modular decomposition and transitive orientation
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• Approximation of knapsack problems with conflict and forcing graphs
• Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Graph Classes: A Survey
• Independence and Efficient Domination on P₆-free Graphs
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Transitiv orientierbare Graphen
• Independent Sets of Maximum Weight in Apple-Free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Combining decomposition approaches for the maximum weight stable set problem