independent set problem

On a reduction of the weighted induced bipartite subgraph problem to the weighted independent set problem

  • Shinji Mizuno
  • Yotaro Takazawa
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

    We study the weighted induced bipartite subgraph problem (WIBSP). The goal of WIBSP is, given a graph and nonnegative weights for the nodes, to find a set W of nodes with the maximum total weight such that a subgraph induced by W is bipartite. WIBSP is also referred as to the graph bipartization problem or … Read more