On domination problems for permutation and other graphs
From MaRDI portal
Publication:1100915
DOI10.1016/0304-3975(87)90128-9zbMath0641.68100MaRDI QIDQ1100915
Andreas Brandstädt, Dieter Kratsch
Publication date: 1987
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(87)90128-9
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Generate all maximal independent sets in permutation graphs, Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs, On the feedback vertex set problem for a planar graph, Dominating sets in perfect graphs, Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs, The weighted maximum independent set problem in permutation graphs, The complexity of domination problems in circle graphs, On the algorithmic complexity of twelve covering and independence parameters of graphs, A theorem on permutation graphs with applications, On the feedback vertex set problem in permutation graphs, \(r\)-dominating cliques in graphs with hypertree structure, A note on \(r\)-dominating cliques, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Independent domination in finitely defined classes of graphs, An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs, Coloring permutation graphs in parallel, Independent sets in extensions of 2\(K_{2}\)-free graphs, Fast algorithms for the dominating set problem on permutation graphs, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem