A combinatorial algorithm for weighted stable sets in bipartite graphs

DOI10.1016/j.dam.2005.05.037zbMath1138.90491OpenAlexW2085144892MaRDI QIDQ2492214

Gereon Frahling, Ulrich Faigle

Publication date: 9 June 2006

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

Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.037

zbMATH Keywords

bipartite graphstable settree solution

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (8)

Claw‐free circular‐perfect graphs ⋮ \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs ⋮ The clique problem with multiple-choice constraints under a cycle-free dependency graph ⋮ Allocation of indivisible items with individual preference graphs ⋮ The symmetric quadratic traveling salesman problem ⋮ Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs ⋮ Level of repair analysis and minimum cost homomorphisms of graphs ⋮ Variational approximations in geoadditive latent Gaussian regression: mean and quantile regression

Cites Work

• Unnamed Item
• Unnamed Item
• Matching theory
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• A new?old algorithm for minimum-cut and maximum-flow in closure graphs
• Network Flow and Testing Graph Connectivity

This page was built for publication: A combinatorial algorithm for weighted stable sets in bipartite graphs