Clustering and domination in perfect graphs

DOI10.1016/0166-218X(84)90088-XzbMath0581.05053OpenAlexW2006278018MaRDI QIDQ1068110

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(84)90088-x

zbMATH Keywords

algorithms bipartite graphs chordal graphs cographs split graphs NP completeness comparability graphs k-cluster problem k-dominating set problem k-trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width, Computing role assignments of split graphs, On the independent dominating set polytope, Well-partitioned chordal graphs, On domination problems for permutation and other graphs, On semi-$P_ 4$-sparse graphs, Approximation of the Quadratic Knapsack Problem, Computational results of a semidefinite branch-and-bound algorithm for $k$-cluster, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Monopolar graphs: complexity of computing classical graph parameters, Finding a maximum minimal separator: graph classes and fixed-parameter tractability, Complexity and approximability of the happy set problem, Finding connected $k$-subgraphs with high density, Solving $k$-cluster problems to optimality with semidefinite programming, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, Graph classes with structured neighborhoods and algorithmic applications, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, Finding Connected Dense $$k$$-Subgraphs, Further results on the independent Roman domination number of graphs, Finding clubs in graph classes, Computing densest $k$-subgraph with structural parameters, Maximum weight independent sets for ($P_7$,triangle)-free graphs in polynomial time, Edge deletion to tree-like graph classes, Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs, Treewidth versus clique number. II: Tree-independence number, The densest $k$-subgraph problem on clique graphs, FPT approximation and subexponential algorithms for covering few or many edges, The \textsc{max quasi-independent set} problem, Exact capacitated domination: on the computational complexity of uniqueness, On inclusionwise maximal and maximum cardinality $k$-clubs in graphs, Unnamed Item, Domination and total domination on asteroidal triple-free graphs, Exact algorithms for problems related to the densest $k$-set problem, The maximum vertex coverage problem on bipartite graphs, Structural domination and coloring of some $( P_7 , C_7)$-free graphs, Dominating sets in perfect graphs, Permutation graphs: Connected domination and Steiner trees, Convex Optimization for Group Feature Selection in Networked Data, Independent dominating set problem revisited, Well-indumatched Trees and Graphs of Bounded Girth, An optimal algorithm for finding dominating cycles in circular-arc graphs, Exploring the complexity boundary between coloring and list-coloring, Quantum solutions for densest $k$-subgraph problems, The minimum weakly connected independent set problem: polyhedral results and branch-and-cut, An O($n$) time algorithm for maximum matching on cographs, Total domination in interval graphs, A ``maximum node clustering problem, Algorithms for dominating clique problems, Small $k$-pyramids and the complexity of determining $k$, A constant approximation algorithm for the densest $k$-subgraph problem on chordal graphs, A matrix characterization of interval and proper interval graphs, Parameterized algorithms for the happy set problem, The complexity of domination problems in circle graphs, Paired-domination problem on distance-hereditary graphs, Upper bounds and exact algorithms for $p$-dispersion problems, Intersection graphs of non-crossing paths, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Graph classes and approximability of the happy set problem, Uniqueness of $DP$-Nash subgraphs and $D$-sets in weighted graphs of Netflix games, Smallest independent dominating sets in Kronecker products of cycles, Network flow interdiction on planar graphs, The complexity of the defensive domination problem in special graph classes, A polyhedral study of the maximum edge subgraph problem, Secure total domination in graphs: bounds and complexity, Threshold-based preprocessing for approximating the weighted dense $k$-subgraph problem, On the inapproximability of independent domination in $2P_3$-free perfect graphs, On 3-coloring of $(2P_4,C_5)$-free graphs, A new upper bound for the 0-1 quadratic knapsack problem, A branch-and-bound approach for maximum quasi-cliques, On 3-coloring of $(2P_4,C_5)$-free graphs, Connected Domination, Distance Domination in Graphs, An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph, Online Maximum k-Coverage, Weighted connected domination and Steiner trees in distance-hereditary graphs, Variable neighborhood search for the heaviest $k$-subgraph, Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method, Constant factor approximation algorithms for the densest $k$-subgraph problem on proper interval graphs and bipartite permutation graphs, Unnamed Item, Unnamed Item, Partial and perfect path covers of cographs, Graph Classes with Structured Neighborhoods and Algorithmic Applications, On the algorithmic complexity of twelve covering and independence parameters of graphs, Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs, Mind the independence gap, On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm, On solving the densestk-subgraph problem on large graphs, Finding minimum dominating cycles in permutation graphs, Independent Domination in Triangle Graphs, A polynomial algorithm for the k-cluster problem on the interval graphs, A linear time algorithm for the maximum matching problem on cographs, Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, On cocolourings and cochromatic numbers of graphs, Bibliography on domination in graphs and some basic definitions of domination parameters, Well-covered graphs and extendability, Approximating the \textsc{Sparsest} $k$-\textsc{Subgraph} in chordal graphs, PTAS for densest $k$-subgraph in interval graphs

Cites Work