標題: On Complexity of Total Vertex Cover on Subcubic Graphs
作者: Poon, Sheung-Hung
Wang, Wei-Lin
資訊工程學系
Department of Computer Science
公開日期: 1-一月-2017
摘要: A total vertex cover is a vertex cover whose induced subgraph consists of a set of connected components, each of which contains at least two vertices. A t-total vertex cover is a total vertex cover where each component of its induced subgraph contains at least t vertices. The total vertex cover (TVC) problem and the t-total vertex cover (t-TVC) problem ask for the corresponding cover set with minimum cardinality, respectively. In this paper, we first show that the t-TVC problem is NP-complete for connected subcubic grid graphs of arbitrarily large girth. Next, we show that the t-TVC problem is NP-complete for 3-connected cubic planar graphs. Moreover, we show that the t-TVC problem is APX-complete for connected subcubic graphs of arbitrarily large girth.
URI: http://dx.doi.org/10.1007/978-3-319-55911-7_37
http://hdl.handle.net/11536/146929
ISSN: 0302-9743
DOI: 10.1007/978-3-319-55911-7_37
期刊: THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2017)
Volume: 10185
起始頁: 514
結束頁: 527
顯示於類別:會議論文