The generalized stable set problem for claw-free bidirected graphs

Daishin Nakamura; Akihisa Tamura

doi:10.1007/3-540-69346-7_6

The generalized stable set problem for claw-free bidirected graphs

Daishin Nakamura, Akihisa Tamura

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

Bidirected graphs are a generalization of undirected graphs. The generalized stable set problem is an extension of the maximum weight stable set problem for undirected graphs to bidirected graphs. It is known that the latter problem is polynomially solvable for claw-free undirected graphs. In this paper, we define claw-free bidirected graphs and show that the generalized stable set problem is also polynomially solvable for claw-free bidirected graphs.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer Verlag
Pages	69-83
Number of pages	15
Volume	1412
ISBN (Print)	354064590X, 9783540645900
DOIs	https://doi.org/10.1007/3-540-69346-7_6
Publication status	Published - 1998
Externally published	Yes
Event	6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998 - Houston, United States Duration: 1998 Jun 22 → 1998 Jun 24

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1412
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998
Country/Territory	United States
City	Houston
Period	98/6/22 → 98/6/24

ASJC Scopus subject areas

Computer Science(all)
Theoretical Computer Science

Access to Document

10.1007/3-540-69346-7_6

Cite this

Nakamura, D., & Tamura, A. (1998). The generalized stable set problem for claw-free bidirected graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 1412, pp. 69-83). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1412). Springer Verlag. https://doi.org/10.1007/3-540-69346-7_6

The generalized stable set problem for claw-free bidirected graphs. / Nakamura, Daishin; Tamura, Akihisa.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 1412 Springer Verlag, 1998. p. 69-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1412).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Nakamura, D & Tamura, A 1998, The generalized stable set problem for claw-free bidirected graphs. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 1412, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1412, Springer Verlag, pp. 69-83, 6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998, Houston, United States, 98/6/22. https://doi.org/10.1007/3-540-69346-7_6

Nakamura D, Tamura A. The generalized stable set problem for claw-free bidirected graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 1412. Springer Verlag. 1998. p. 69-83. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-69346-7_6

Nakamura, Daishin ; Tamura, Akihisa. / The generalized stable set problem for claw-free bidirected graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 1412 Springer Verlag, 1998. pp. 69-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4d89289ec8ea4da0bf91b17e6bbde963,

title = "The generalized stable set problem for claw-free bidirected graphs",

abstract = "Bidirected graphs are a generalization of undirected graphs. The generalized stable set problem is an extension of the maximum weight stable set problem for undirected graphs to bidirected graphs. It is known that the latter problem is polynomially solvable for claw-free undirected graphs. In this paper, we define claw-free bidirected graphs and show that the generalized stable set problem is also polynomially solvable for claw-free bidirected graphs.",

author = "Daishin Nakamura and Akihisa Tamura",

year = "1998",

doi = "10.1007/3-540-69346-7_6",

language = "English",

isbn = "354064590X",

volume = "1412",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "69--83",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

note = "6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998 ; Conference date: 22-06-1998 Through 24-06-1998",

}

TY - GEN

T1 - The generalized stable set problem for claw-free bidirected graphs

AU - Nakamura, Daishin

AU - Tamura, Akihisa

PY - 1998

Y1 - 1998

N2 - Bidirected graphs are a generalization of undirected graphs. The generalized stable set problem is an extension of the maximum weight stable set problem for undirected graphs to bidirected graphs. It is known that the latter problem is polynomially solvable for claw-free undirected graphs. In this paper, we define claw-free bidirected graphs and show that the generalized stable set problem is also polynomially solvable for claw-free bidirected graphs.

AB - Bidirected graphs are a generalization of undirected graphs. The generalized stable set problem is an extension of the maximum weight stable set problem for undirected graphs to bidirected graphs. It is known that the latter problem is polynomially solvable for claw-free undirected graphs. In this paper, we define claw-free bidirected graphs and show that the generalized stable set problem is also polynomially solvable for claw-free bidirected graphs.

UR - http://www.scopus.com/inward/record.url?scp=84958761126&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958761126&partnerID=8YFLogxK

U2 - 10.1007/3-540-69346-7_6

DO - 10.1007/3-540-69346-7_6

M3 - Conference contribution

AN - SCOPUS:84958761126

SN - 354064590X

SN - 9783540645900

VL - 1412

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 69

EP - 83

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer Verlag

T2 - 6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998

Y2 - 22 June 1998 through 24 June 1998

ER -

The generalized stable set problem for claw-free bidirected graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this