On graphs with polynomially solvable maximum-weight clique problem
From MaRDI portal
Publication:3809822
DOI10.1002/net.3230190206zbMath0661.05036OpenAlexW2030398678MaRDI QIDQ3809822
Publication date: 1989
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230190206
Related Items
Independent domination in hereditary classes, Independent sets of maximum weight in (\(p,q\))-colorable graphs., The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable, 4-Coloring H-Free Graphs When H Is Small, Blocker size via matching minors, Scheduling independent tasks with multiple modes, Graphs with maximal induced matchings of the same size, New applications of clique separator decomposition for the maximum weight stable set problem, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem, From matchings to independent sets, The maximum independent union of cliques problem: complexity and exact approaches, More results on weighted independent domination, Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity, Unique key Horn functions, Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs, Independent domination in finitely defined classes of graphs, Graphs of separability at most 2, The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size, Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time, Algorithms for induced biclique optimization problems, Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time, An inequality for polymatroid functions and its applications., On easy and hard hereditary classes of graphs with respect to the independent set problem, Complexity and algorithms for recognizing polar and monopolar graphs, Reconfiguration of cliques in a graph, Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, On the parameterized complexity of coloring graphs in the absence of a linear forest, Clique problem, cutting plane proofs and communication complexity, Well-indumatched Trees and Graphs of Bounded Girth, Shuffling biological sequences with motif constraints, Graphs of Separability at Most Two: Structural Characterizations and Their Consequences, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, Independent sets in graphs, Simple games versus weighted voting games: bounding the critical threshold value, The critical node detection problem in networks: a survey, Maximum weight edge-constrained matchings, Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs, Stability number in subclasses of \(P_5\)-free graphs, Minimum cost and list homomorphisms to semicomplete digraphs, An upper bound for the number of maximal independent sets in a graph, On the complexity of the independent set problem in triangle graphs, The complexity of dissociation set problems in graphs, Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs, Colouring Vertices of Triangle-Free Graphs, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, Connected vertex cover for \((sP_1+P_5)\)-free graphs, On cycle transversals and their connected variants in the absence of a small linear forest, Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs, Strong cliques in diamond-free graphs, Extension of hereditary classes with substitutions, Updating the complexity status of coloring graphs without a fixed induced linear forest, Colouring vertices of triangle-free graphs without forests, Bounding the number of circuits of a graph, Parameterized complexity of the maximum independent set problem and the speed of hereditary properties, On efficient domination for some classes of \(H\)-free bipartite graphs, Squares of Intersection Graphs and Induced Matchings, On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs, The maximum clique problem, The \(k\)-separator problem: polyhedra, complexity and approximation results, The clique problem for graphs with a few eigenvalues of the same sign
Cites Work
