Struction revisited

DOI10.1016/S0166-218X(03)00388-3MaRDI QIDQ1414580zbMATH OpenOpenAlexFDO

Authors Gabriela Alexe, Peter L. Hammer, Dominique De Werra, Vadim Lozin

Publication date 4 December 2003

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

Full work available at URL https://doi.org/10.1016/s0166-218x(03)00388-3

zbMATH Keywords

Graph transformationStability numberStable set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 4088925
• Structural reductions revisited
• Structures and Structural Realism
• scientific article; zbMATH DE number 1254496
• scientific article; zbMATH DE number 1058080
• Publication:4955961
• Structure and Equivalence

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• An augmentation algorithm for the maximum weighted stable set problem
• An upper bound on the number of cliques in a graph
• Conic reduction of graphs for the stable set problem
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3904619 (Why is no real title available?)
• scientific article; zbMATH DE number 3943843 (Why is no real title available?)
• scientific article; zbMATH DE number 1512194 (Why is no real title available?)
• scientific article; zbMATH DE number 956849 (Why is no real title available?)
• Matching theory
• On Some Properties of the Struction of a Graph
• On the stability number of AH‐free graphs
• On the stability number of claw-free \(P_5\)-free and more general graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• On the use of Boolean methods for the computation of the stability number
• Paths, Trees, and Flowers
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Polynomially solvable cases for the maximum stable set problem
• Quelques utilisations de la STRUCTION. (Some applications of STRUCTION)
• Stability in \(P_5\)- and banner-free graphs
• Stability in CAN-free graphs
• Stability in circular arc graphs
• Stability number of bull- and chair-free graphs
• The basic algorithm for pseudo-Boolean programming revisited
• The struction algorithm for the maximum stable set problem revisited
• The struction of a graph: Application to CN-free graphs
• Vertex cover: Further observations and further improvements

Cited in

(18)

• The struction of a graph: Application to CN-free graphs
• Quelques utilisations de la STRUCTION. (Some applications of STRUCTION)
• The struction algorithm for the maximum stable set problem revisited
• The maximum independent set problem in subclasses of subcubic graphs
• From matchings to independent sets
• On Some Properties of the Struction of a Graph
• scientific article; zbMATH DE number 4081747 (Why is no real title available?)
• scientific article; zbMATH DE number 486771 (Why is no real title available?)
• Weighted stability number of graphs and weighted satisfiability: the two facets of pseudo-Boolean optimization
• Graph transformations preserving the stability number
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Graph transformations preserving the stability number
• On the structure of Skipjack
• Edge cover by connected bipartite subgraphs
• Stability preserving transformations of graphs
• A folding preprocess for the max k-cut problem
• There and back again: on applying data reduction rules by undoing others
• Finding near-optimal weight independent sets at scale

This page was built for publication: Struction revisited

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