講演抄録/キーワード |
講演名 |
2012-07-03 09:50
On Minimum Feedback Vertex Sets in Graphs ○Asahi Takaoka・Satoshi Tayu・Shuichi Ueno(Tokyo Inst. of Tech.) CAS2012-16 VLD2012-26 SIP2012-48 MSS2012-16 |
抄録 |
(和) |
For the minimum feedback vertex set problem, we show a linear time algorithm for bipartite permutation graphs, the NP-hardness for grid intersection graphs, and a polynomial time algorithm for graphs with maximum degree at most three. |
(英) |
For the minimum feedback vertex set problem, we show a linear time algorithm for bipartite permutation graphs, the NP-hardness for grid intersection graphs, and a polynomial time algorithm for graphs with maximum degree at most three. |
キーワード |
(和) |
2部置換グラフ / 帰還点集合 / 格子交差グラフ / マトロイドパリティ問題 / / / / |
(英) |
bipartite permutation graph / feedback vertex set / grid intersection graph / matroid parity problem / / / / |
文献情報 |
信学技報, vol. 112, no. 113, CAS2012-16, pp. 87-92, 2012年7月. |
資料番号 |
CAS2012-16 |
発行日 |
2012-06-25 (CAS, VLD, SIP, MSS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CAS2012-16 VLD2012-26 SIP2012-48 MSS2012-16 |
|