2011/11/29 by Chun-Ying Chiang, Chiang, Chun-Ying, Liang-Hao Huang +7 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Search Problems #Social and Information Networks (cs.SI) #cs.CC #cs.DM #cs.DS #cs.SI #math.CO
paper · pdf · doi:10.48550/arxiv.1111.6685
arxiv created 2011/11/29 · openalex publication_date 2011/11/29 · arxiv updated 2011/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we consider a fundamental problem in the area of viral marketing, called T\scriptsize ARGET S\scriptsize ET S\scriptsize ELECTION problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if G is a block-cactus graph, then the T\scriptsize ARGET S\scriptsize ET S\scriptsize ELECTION problem can be solved in linear time, which generalizes Chen's result \citechen2009 for trees, and the time complexity is much better than the algorithm in \citetreewidth (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph G is a chordal graph with thresholds θ(v)≤ 2 for each vertex v in G, then the problem can be solved in linear time. For a Hamming graph G having thresholds θ(v)=2 for each vertex v of G, we precisely determine an optimal target set S for (G,θ). These results partially answer an open problem raised by Dreyer and Roberts \citeDreyer2009.