On domination problems for permutation and other graphs
From MaRDI portal
Publication:1100915
DOI10.1016/0304-3975(87)90128-9zbMath0641.68100OpenAlexW2080076699MaRDI QIDQ1100915
Dieter Kratsch, Andreas Brandstädt
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (35)
Coloring permutation graphs in parallel ⋮ A theorem on permutation graphs with applications ⋮ Fast algorithms for the dominating set problem on permutation graphs ⋮ A linear-time algorithm for the weighted feedback vertex problem on interval graphs ⋮ On the independent dominating set polytope ⋮ On the feedback vertex set problem in permutation graphs ⋮ Dominating cliques in distance-hereditary graphs ⋮ r-Domination problems on homogeneously orderable graphs ⋮ Complexity aspects of generalized Helly hypergraphs ⋮ The NP-completeness of Steiner tree and dominating set for chordal bipartite 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 ⋮ Generate all maximal independent sets in permutation graphs ⋮ On the domination number of permutation graphs and an application to strong fixed points ⋮ Dominating sets in perfect graphs ⋮ Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs ⋮ Feedback vertex set on AT-free graphs ⋮ On the feedback vertex set problem for a planar graph ⋮ The weighted maximum independent set problem in permutation graphs ⋮ The complexity of domination problems in circle graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem ⋮ Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs ⋮ Hardness results and approximation algorithm for total liar's domination in graphs ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ A survey of selected recent results on total domination in graphs ⋮ The \(k\)-power domination problem in weighted trees ⋮ An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ Independent Domination in Triangle Graphs ⋮ Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ On connected dominating sets of restricted diameter
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Weakly triangulated graphs
- Finding minimum dominating cycles in permutation graphs
- Clustering and domination in perfect graphs
- Bipartite permutation graphs
- Permutation graphs: Connected domination and Steiner trees
- Domination in permutation graphs
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Permutation Graphs and Transitive Graphs
- The NP-completeness column: An ongoing guide
This page was built for publication: On domination problems for permutation and other graphs
