Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

DOI10.1137/0201013zbMath0227.05116MaRDI 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

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C15: Coloring of graphs and hypergraphs

05-04: Software, source code, etc. for problems pertaining to combinatorics

Related Items

Weighted maximum-clique transversal sets of graphs, Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models, Optimization problems in multiple subtree graphs, Separator orders in interval, cocomparability, and AT-free graphs, Minimum vertex cover in rectangle graphs, Some properties of graphs determined by edge zeta functions, Leader localization in multi-agent systems subject to failure: a graph-theoretic approach, On recognizing and characterizing visibility graphs of simple polygons, Computing role assignments of chordal graphs, On finding a minimum vertex cover of a series-parallel graph, Maximum induced matching problem on hhd-free graphs, Some aspects of perfect elimination orderings in chordal graphs, Finding maximum cliques in arbitrary and in special graphs, Penta-extensions of hereditary classes of graphs, Maximizing the weighted number of just-in-time jobs in flow shop scheduling, Optimal register allocation for SSA-form programs in polynomial time, Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time, Maximizing weighted number of just-in-time jobs on unrelated parallel machines, Job distribution algorithms, Covering orthogonal polygons with star polygons: The perfect graph approach, Approximating the 2-interval pattern problem, Counting the number of independent sets in chordal graphs, Two methods for the generation of chordal graphs, A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs, On split-coloring problems, On the parameterized complexity of multiple-interval graph problems, Center location problems on tree graphs with subtree-shaped customers, A linear time recognition algorithm for proper interval graphs, Scheduling with a minimum number of machines, The \(S\)-digraph optimization problem and the greedy algorithm, Laminar structure of ptolemaic graphs with applications, Large independent sets in random regular 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, Concerning the achromatic number of graphs, Clustering and domination in perfect graphs, \(K_ i\)-covers. I: Complexity and polytopes, Intersection graphs of paths in a tree, Linear time algorithms for NP-hard problems restricted to partial k- trees, Labeling algorithms for domination problems in sun-free chordal graphs, An application of vertex packing to data analysis in the evaluation of pavement deterioration, The edge Hamiltonian path problem is NP-complete, Locational analysis, Finding a minimal cover for binary images: An optimal parallel algorithm, Studies on hypergraphs. I: Hyperforests, An algorithm for testing chordality of graphs, A recognition algorithm for the intersection graphs of directed paths in directed trees, A note on the complexity of the chromatic number problem, Some simplified NP-complete graph problems, Comparability graphs and a new matroid, Efficient Algorithms for (3,1) Graphs, The complexity of comparability graph recognition and coloring, Algorithms on clique separable graphs, Linear algorithms on recursive representations of trees, A recognition algorithm for the intersection graphs of paths in trees, The complexity of generalized clique covering, Induced matchings, All structured programs have small tree width and good register allocation, On the algorithmic complexity of twelve covering and independence parameters of graphs, On some optimization problems on \(k\)-trees and partial \(k\)-trees, The maximum clique problem, Monadic second-order definable graph transductions: a survey, Intersection graphs of concatenable subtrees of graphs, The struction algorithm for the maximum stable set problem revisited, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, New linear time algorithms for generating perfect elimination orderings of chordal graphs, Proper interval graphs and the guard problem, Maximum vertex-weighted matching in strongly chordal graphs, Induced matchings in intersection graphs., Enumerating all connected maximal common subgraphs in two graphs, Stability number in subclasses of \(P_5\)-free graphs, An algorithm for source location in directed graphs, Chromatic numbers of competition graphs, On a 2-dimensional equipartition problem, Parameterized complexity of vertex colouring, Graph-theoretical properties of parallelism in the digital plane, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Proper interval vertex deletion, Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs, New results on induced matchings, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, On the complexity of the independent set problem in triangle graphs, The complexity of dissociation set problems in graphs, A faster algorithm to recognize undirected path graphs, The densest \(k\)-subgraph problem on clique graphs, A scheme for computing minimum covers within simple regions, Variations of maximum-clique transversal sets on graphs, On guarding the vertices of rectilinear domains, Tree decomposition and discrete optimization problems: a survey, The intersection graphs of subtrees in trees are exactly the chordal graphs, One-way and round-trip center location problems, Independent packings in structured graphs, A Scheme for Computing Minimum Covers within Simple Regions, A Note on k-Colorability of P 5-Free Graphs, The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs, Convexity in Graphs and Hypergraphs, A Dynamic Programming Approach to the Dominating Set Problem on k-Trees, A parallel algorithm to generate all maximal independent sets on permutation graphs, Using Fifth Generation Tools for Solving the Clique Number Problem, SCHEDULING INTERVAL ORDERS IN PARALLEL, On the existence of convex decompositions of partially separable functions, Structural Learning with Time-Varying Components: Tracking the Cross-Section of Financial Time Series, On the complexity of alpha conversion, Heuristic and metaheuristic methods for computing graph treewidth, Unnamed Item, On coloring problems with local constraints, On coloring problems with local constraints, A branch and bound algorithm for the maximum clique problem, A note on \(\alpha\)-redundant vertices in graphs, Approximation algorithms for maximum two-dimensional pattern matching, Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs, A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles, Polynomially bounded algorithms for locatingp-centers on a tree, An algorithm for the maximum internally stable set in a weighted graph, ?-Perfect graphs, Vertex packings: Structural properties and algorithms