| Article ID: | iaor2001986 |
| Country: | Japan |
| Volume: | 43 |
| Issue: | 1 |
| Start Page Number: | 162 |
| End Page Number: | 175 |
| Publication Date: | Mar 2000 |
| Journal: | Journal of the Operations Research Society of Japan |
| Authors: | Tamura Akihisa, Nakamura Daishin |
| Keywords: | graphs, programming: integer, programming: linear |
The generalized stable set problem is an extension of the maximum weight stable set problem for undirected graphs to bidirected graphs. This paper shows that the problem on triangulated bidirected graphs is solvable in linear time. We also propose an exact branch and bound algorithm for the general problem by applying the linear time algorithm.