TY - GEN
T1 - Tractable connected domination for restricted bipartite graphs (extended abstract)
AU - Lu, Zhao
AU - Liu, Tian
AU - Xu, Ke
PY - 2013
Y1 - 2013
N2 - Finding a minimum connected dominating set (connected domination) is known-complete for chordal bipartite graphs, but tractable for convex bipartite graphs. In this paper, connected domination is shown tractable for circular-and triad-convex bipartite graphs, by efficient reductions from these graphs to convex bipartite graphs.
AB - Finding a minimum connected dominating set (connected domination) is known-complete for chordal bipartite graphs, but tractable for convex bipartite graphs. In this paper, connected domination is shown tractable for circular-and triad-convex bipartite graphs, by efficient reductions from these graphs to convex bipartite graphs.
KW - Connected domination
KW - circular-convex bipartite graph
KW - convex bipartite graph
KW - polynomial-time
KW - triad-convex bipartite graph
UR - https://www.scopus.com/pages/publications/84884919170
U2 - 10.1007/978-3-642-38768-5_65
DO - 10.1007/978-3-642-38768-5_65
M3 - 会议稿件
AN - SCOPUS:84884919170
SN - 9783642387678
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 721
EP - 728
BT - Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings
T2 - 19th International Computing and Combinatorics Conference, COCOON 2013
Y2 - 21 June 2013 through 21 June 2013
ER -