2016年1月
An exact algorithm for maximum independent set in degree-5 graphs
DISCRETE APPLIED MATHEMATICS
- ,
- 巻
- 199
- 号
- 開始ページ
- 137
- 終了ページ
- 155
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.dam.2014.07.009
- 出版者・発行元
- ELSEVIER SCIENCE BV
The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks of the problem in general graphs. In this paper, we present a 1.1736(n)n(0(1))-time exact algorithm for the maximum independent set problem in an n-vertex graph with degree bounded by 5, improving the previous running time bound of 1.1895(n)n(0(1)). In our algorithm, we show that the graph after applying reduction rules always has a good local structure branching on which will effectively reduce the instance. Based on this, we obtain an improved algorithm without introducing a large number of branching rules. (C) 2014 Elsevier B.V. All rights reserved.
- リンク情報
-
- DOI
- https://doi.org/10.1016/j.dam.2014.07.009
- DBLP
- https://dblp.uni-trier.de/rec/journals/dam/XiaoN16
- J-GLOBAL
- https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201702200977977235
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000368045700011&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/dam/dam199.html#journals/dam/XiaoN16
- ID情報
-
- DOI : 10.1016/j.dam.2014.07.009
- ISSN : 0166-218X
- eISSN : 1872-6771
- DBLP ID : journals/dam/XiaoN16
- J-Global ID : 201702200977977235
- Web of Science ID : WOS:000368045700011