2014/07/08 by Mamadou Moustapha Kanté, Kanté, Mamadou Moustapha, Vincent Limouzy +7
Computer Science · #05C30 #05C69 #05C85 #68P05 #68R10 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #E.1 #F.0 #FOS: Computer and information sciences #G.2.2 #acm:05C30 #acm:05C69 #acm:05C85 #acm:68P05 #acm:68R10 #cs.DM #cs.DS #msc:05C30 #msc:05C69 #msc:05C85 #msc:68P05 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1407.2036
13 pages, 1 figure, submitted
arxiv created 2014/07/08 · arxiv updated 2014/07/09
An output-polynomial algorithm for the listing of minimal dominating sets in graphs is a challenging open problem and is known to be equivalent to the well-known Transversal problem which asks for an output-polynomial algorithm for listing the set of minimal hitting sets in hypergraphs. We give a polynomial delay algorithm to list the set of minimal dominating sets in chordal graphs, an important and well-studied graph class where such an algorithm was open for a while.