Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
From MaRDI portal
Publication:5634016
DOI10.1137/0201013zbMath0227.05116OpenAlexW1973310391MaRDI QIDQ5634016
Publication date: 1972
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0201013
Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items
The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs, An algorithm for the maximum internally stable set in a weighted graph, Linear-Time Generation of Random Chordal Graphs, A faster algorithm to recognize undirected path graphs, Model Rejection and Parameter Reduction via Time Series, Convexity in Graphs and Hypergraphs, A Scheme for Computing Minimum Covers within Simple Regions, Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation, Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems, SCHEDULING INTERVAL ORDERS IN PARALLEL, Structural Learning with Time-Varying Components: Tracking the Cross-Section of Financial Time Series, On graphs whose eternal vertex cover number and vertex cover number coincide, ?-Perfect graphs, Using edge contractions and vertex deletions to reduce the independence number and the clique number, On Strict (Outer-)Confluent Graphs, Query-competitive sorting with uncertainty, Perfect elimination orderings for symmetric matrices, Exploiting sparsity for the min \(k\)-partition problem, Approximation and Kernelization for Chordal Vertex Deletion, A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree, Independent set under a change constraint from an initial solution, Coloring \((4K_1,C_4,C_6)\)-free graphs, Reducing graph parameters by contractions and deletions, Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs, Vertex cover in conflict graphs, Round-competitive algorithms for uncertainty problems with parallel queries, Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs, Approximating the chromatic polynomial of a graph, A Dynamic Programming Approach to the Dominating Set Problem on k-Trees, The densest \(k\)-subgraph problem on clique graphs, On the tractability of optimization problems on \(H\)-graphs, Unnamed Item, A scheme for computing minimum covers within simple regions, On groups with chordal power graph, including a classification in the case of finite simple groups, Variations of maximum-clique transversal sets on graphs, One-sided terrain guarding and chordal graphs, On the structure of (pan, even hole)‐free graphs, Unnamed Item, A Refined Analysis of Online Path Coloring in Trees, A Lower Bound of the cd-Chromatic Number and Its Complexity, On strict (outer-)confluent graphs, Distance-\(d\) independent set problems for bipartite and chordal graphs, Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs, On coloring problems with local constraints, Vertex packings: Structural properties and algorithms, On coloring problems with local constraints, Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension, Latent association graph inference for binary transaction data, Edge clique partition in \((k,\ell)\)-graphs, Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams., On guarding the vertices of rectilinear domains, A branch and bound algorithm for the maximum clique problem, Tree decomposition and discrete optimization problems: a survey, A note on \(\alpha\)-redundant vertices in graphs, A parallel algorithm to generate all maximal independent sets on permutation graphs, Chordality of graphs associated to commutative rings, Approximation algorithms for maximum two-dimensional pattern matching, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, On the existence of convex decompositions of partially separable functions, A Note on k-Colorability of P 5-Free Graphs, On the complexity of the independent set problem in triangle graphs, The complexity of dissociation set problems in graphs, On the complexity of alpha conversion, Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs, Layered graphs: applications and algorithms, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Maximum independent sets in subcubic graphs: new results, The Private Neighbor Concept, Using Fifth Generation Tools for Solving the Clique Number Problem, A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles, Independent Set Reconfiguration in Cographs and their Generalizations, Heuristic and metaheuristic methods for computing graph treewidth, Query-Competitive Sorting with Uncertainty., Unnamed Item, Improper sum-list colouring of 2-trees, The intersection graphs of subtrees in trees are exactly the chordal graphs, Computing the 2-blocks of directed graphs, One-way and round-trip center location problems, Computing 2-twinless blocks, Independent packings in structured graphs, Polynomially bounded algorithms for locatingp-centers on a tree, Vertex Deletion Problems on Chordal Graphs, Monadic second-order definable graph transductions: a survey, Intersection graphs of paths in a tree, Intersection graphs of concatenable subtrees of graphs, The struction algorithm for the maximum stable set problem revisited, A linear-time algorithm for the weighted feedback vertex problem on interval graphs, A generalization of chordal graphs and the maximum clique problem, One-sided discrete terrain guarding and chordal graphs, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, The recognition of geodetically connected graphs, Maximizing the weighted number of just-in-time jobs in flow shop scheduling, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Optimal approximation algorithms for maximum distance-bounded subgraph problems, Optimal register allocation for SSA-form programs in polynomial time, New linear time algorithms for generating perfect elimination orderings of chordal graphs, Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time, Proper interval graphs and the guard problem, Linear time algorithms for NP-hard problems restricted to partial k- trees, Labeling algorithms for domination problems in sun-free chordal graphs, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Maximizing weighted number of just-in-time jobs on unrelated parallel machines, Approximation for vertex cover in \(\beta\)-conflict graphs, Job distribution algorithms, Maximum vertex-weighted matching in strongly chordal graphs, Complexity of finding maximum regular induced subgraphs with prescribed degree, Weighted maximum-clique transversal sets of graphs, Some properties of graphs determined by edge zeta functions, Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models, A hybrid tractable class for non-binary CSPs, Proper interval vertex deletion, Combining restarts, nogoods and bag-connected decompositions for solving csps, Leader localization in multi-agent systems subject to failure: a graph-theoretic approach, Covering orthogonal polygons with star polygons: The perfect graph approach, An application of vertex packing to data analysis in the evaluation of pavement deterioration, Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs, The edge Hamiltonian path problem is NP-complete, Induced matchings in intersection graphs., Locational analysis, Finding a minimal cover for binary images: An optimal parallel algorithm, Approximation algorithms for intersection graphs, Approximating the 2-interval pattern problem, Counting the number of independent sets in chordal graphs, New results on induced matchings, Evader interdiction: algorithms, complexity and collateral damage, On the kernel size of clique cover reductions for random intersection graphs, Two methods for the generation of chordal graphs, On recognizing and characterizing visibility graphs of simple polygons, Computational complexity of the vertex cover problem in the class of planar triangulations, On the algorithmic aspects of strong subcoloring, Optimization problems in multiple subtree graphs, A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs, Separator orders in interval, cocomparability, and AT-free graphs, Studies on hypergraphs. I: Hyperforests, Stability number in subclasses of \(P_5\)-free graphs, An algorithm for testing chordality of graphs, Minimum vertex cover in rectangle graphs, A recognition algorithm for the intersection graphs of directed paths in directed trees, Computing role assignments of chordal graphs, A note on the complexity of the chromatic number problem, Some simplified NP-complete graph problems, An algorithm for source location in directed graphs, Comparability graphs and a new matroid, Vertex deletion problems on chordal graphs, Efficient Algorithms for (3,1) Graphs, The complexity of comparability graph recognition and coloring, On split-coloring problems, Algorithms on clique separable graphs, On the parameterized complexity of multiple-interval graph problems, Linear algorithms on recursive representations of trees, Center location problems on tree graphs with subtree-shaped customers, A recognition algorithm for the intersection graphs of paths in trees, Graphs without large apples and the maximum weight independent set problem, Chromatic numbers of competition graphs, On a 2-dimensional equipartition problem, The complexity of generalized clique covering, A linear time recognition algorithm for proper interval graphs, Induced matchings, Scheduling with a minimum number of machines, Parameterized complexity of vertex colouring, The \(S\)-digraph optimization problem and the greedy algorithm, All structured programs have small tree width and good register allocation, On finding a minimum vertex cover of a series-parallel graph, Laminar structure of ptolemaic graphs with applications, Maximum induced matching problem on hhd-free graphs, Large independent sets in random regular graphs, On the algorithmic complexity of twelve covering and independence parameters of graphs, Mind the independence gap, Some aspects of perfect elimination orderings in chordal graphs, Enumerating all connected maximal common subgraphs in two graphs, On powers and centers of chordal graphs, NP-complete problems simplified on tree schemas, Decomposition by clique separators, Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey, Graph-theoretical properties of parallelism in the digital plane, Concerning the achromatic number of graphs, On some optimization problems on \(k\)-trees and partial \(k\)-trees, Finding maximum cliques in arbitrary and in special graphs, Clustering and domination in perfect graphs, The maximum clique problem, \(K_ i\)-covers. I: Complexity and polytopes, Penta-extensions of hereditary classes of graphs
