Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time

DOI10.1016/j.dam.2017.10.003zbMath1377.05185arXiv1511.08066OpenAlexW2962704386MaRDI QIDQ1693130

Raffaele Mosca, Andreas Brandstädt

Publication date: 11 January 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.08066

zbMATH Keywords

polynomial time algorithmgraph algorithmstriangle-free graphsmaximum weight independent set problem\(P_7\)-free graphsanti-neighborhood approach

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items (4)

(Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new characterization of \(P_k\)-free graphs
• On maximum independent sets in \(P_{5}\)-free graphs
• Weighted independent sets in a subclass of \(P_6\)-free graphs
• On the closure of triangle-free graphs under substitution
• A new characterization of \(P_{6}\)-free graphs
• Complete description of forbidden subgraphs in the structural domination problem
• Some results on graphs without long induced paths
• Clustering and domination in perfect graphs
• Paw-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• NP-completeness of some generalizations of the maximum matching problem
• Dominating cliques in \(P_ 5\)-free graphs
• Geometric algorithms and combinatorial optimization
• Modular decomposition and transitive orientation
• Stable sets in certain \(P_6\)-free graphs
• Dominating subgraphs in graphs with some forbidden structures
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Stable sets in two subclasses of banner-free graphs
• Triangle-free graphs and forbidden subgraphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• A note on triangle-free and bipartite graphs
• Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• 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
• A characterization of graphs without long induced paths
• Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• On the diameter ofi-center in a graph without long induced paths
• Graph Classes: A Survey
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Independence and Efficient Domination on P₆-free Graphs
• Stable sets for (P_{6}, K_{2,3})-free graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time