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 (98)

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 ⋮ Sparse graphs with bounded induced cycle packing number have logarithmic treewidth ⋮ 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

This page was built for publication: Clustering and domination in perfect graphs