Domination in permutation graphs
From MaRDI portal
Publication:3731637
DOI10.1016/0196-6774(85)90001-XzbMath0598.05056MaRDI QIDQ3731637
Publication date: 1985
Published in: Journal of Algorithms (Search for Journal in Brave)
permutation graphsdomination problemsweighted domination problemcardinality domination problemweighted independent domination problems
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Independent domination in hereditary classes, Coloring permutation graphs in parallel, A theorem on permutation graphs with applications, Fast algorithms for the dominating set problem on permutation graphs, On the independent dominating set polytope, On the feedback vertex set problem in permutation graphs, Bipartite permutation graphs, On dominating set of some subclasses of string graphs, The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs, On domination problems for permutation and other graphs, One-node cutsets and the dominating set polytope, An efficient algorithm to solve the distancek-domination problem on permutation graphs, Induced star partition of graphs, An efficient algorithm for maxdominance, with applications, Labeling algorithms for domination problems in sun-free chordal graphs, Finding a minimum independent dominating set in a permutation graph, Total domination in block graphs, Graph classes with structured neighborhoods and algorithmic applications, Unique response Roman domination: complexity and algorithms, A decidability result for the dominating set problem, Generate all maximal independent sets in permutation graphs, Star covers and star partitions of double-split graphs, On the dominating set polytope, Finding a maximum independent set in a permutation graph, Domination and total domination on asteroidal triple-free graphs, Dominating sets in perfect graphs, Permutation graphs: Connected domination and Steiner trees, An optimal algorithm for finding dominating cycles in circular-arc graphs, Polar SAT and related graphs, The weighted maximum independent set problem in permutation graphs, Incorporating negative-weight vertices in certain vertex-search graph algorithms, Independence and domination in polygon graphs, Computing residual connectedness reliability for restricted networks, Total domination in interval graphs, The complexity of domination problems in circle graphs, Paired-domination problem on distance-hereditary graphs, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, A polynomial-time algorithm for the paired-domination problem on permutation graphs, A new approach for the domination problem on permutation graphs, An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs, Graph Classes with Structured Neighborhoods and Algorithmic Applications, On the algorithmic complexity of twelve covering and independence parameters of graphs, On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm, Domination problems on P5-free graphs, Twin-width and polynomial kernels, Finding minimum dominating cycles in permutation graphs, Parallel algorithms for permutation graphs, Dominating sets and domatic number of circular arc graphs, Clustering and domination in perfect graphs, Bibliography on domination in graphs and some basic definitions of domination parameters, Well-covered graphs and extendability
