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

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Cited In (only showing first 100 items - show all)

Layered graphs: applications and algorithms
Concerning the achromatic number of graphs
The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
Complexity of finding maximum regular induced subgraphs with prescribed degree
Title not available (Why is that?)
Optimization problems in multiple subtree graphs
Minimum vertex cover in rectangle graphs
The maximum clique problem
Weighted maximum-clique transversal sets of graphs
Labeling algorithms for domination problems in sun-free chordal graphs
Computing the 2-blocks of directed graphs
Graphs without large apples and the maximum weight independent set problem
Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs
Maximizing the weighted number of just-in-time jobs in flow shop scheduling
Independent packings in structured graphs
Maximizing weighted number of just-in-time jobs on unrelated parallel machines
A hybrid tractable class for non-binary CSPs
Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
A refined analysis of online path coloring in trees
A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
Decomposition by clique separators
Clustering and domination in perfect graphs
Intersection graphs of paths in a tree
A linear time recognition algorithm for proper interval graphs
The complexity of dissociation set problems in graphs
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
A generalization of chordal graphs and the maximum clique problem
Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
Center location problems on tree graphs with subtree-shaped customers
Proper interval graphs and the guard problem
Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
Intersection graphs of concatenable subtrees of graphs
Linear time algorithms for NP-hard problems restricted to partial k- trees
The recognition of geodetically connected graphs
Structural Learning with Time-Varying Components: Tracking the Cross-Section of Financial Time Series
Some simplified NP-complete graph problems
A Note on k-Colorability of P 5-Free Graphs
Computing role assignments of chordal graphs
Monadic second-order definable graph transductions: a survey
Evader interdiction: algorithms, complexity and collateral damage
Induced matchings
On some optimization problems on \(k\)-trees and partial \(k\)-trees
Approximation algorithms for maximum two-dimensional pattern matching
\(K_ i\)-covers. I: Complexity and polytopes
Subexponential parameterized algorithms and kernelization on almost chordal graphs
On the parameterized complexity of multiple-interval graph problems
The complexity of generalized clique covering
The complexity of comparability graph recognition and coloring
On the complexity of the independent set problem in triangle graphs
Polynomially bounded algorithms for locatingp-centers on a tree
A recognition algorithm for the intersection graphs of directed paths in directed trees
Comparability graphs and a new matroid
Counting the number of independent sets in chordal graphs
A recognition algorithm for the intersection graphs of paths in trees
Linear algorithms on recursive representations of trees
The densest \(k\)-subgraph problem on clique graphs
The struction algorithm for the maximum stable set problem revisited
On guarding the vertices of rectilinear domains
Variations of maximum-clique transversal sets on graphs
On split-coloring problems
Approximation algorithms for intersection graphs
A note on \(\alpha\)-redundant vertices in graphs
Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
On the existence of convex decompositions of partially separable functions
Parameterized complexity of vertex colouring
An algorithm for source location in directed graphs
The intersection graphs of subtrees in trees are exactly the chordal graphs
One-way and round-trip center location problems
Large independent sets in random regular graphs
Locational analysis
Algorithms on clique separable graphs
Covering orthogonal polygons with star polygons: The perfect graph approach
On the algorithmic complexity of twelve covering and independence parameters of graphs
Leader localization in multi-agent systems subject to failure: a graph-theoretic approach
All structured programs have small tree width and good register allocation
On the kernel size of clique cover reductions for random intersection graphs
Convexity in Graphs and Hypergraphs
The edge Hamiltonian path problem is NP-complete
A note on the complexity of the chromatic number problem
Finding maximum cliques in arbitrary and in special graphs
Job distribution algorithms
Induced matchings in intersection graphs.
On recognizing and characterizing visibility graphs of simple polygons
Laminar structure of ptolemaic graphs with applications
Vertex packings: Structural properties and algorithms
New results on induced matchings
Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
Enumerating all connected maximal common subgraphs in two graphs
A faster algorithm to recognize undirected path graphs
The multicolored graph realization problem
Vertex cover in conflict graphs
Independent set reconfiguration in cographs and their generalizations
Efficient Algorithms for (3,1) Graphs
Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
Separator orders in interval, cocomparability, and AT-free graphs
An algorithm for the maximum internally stable set in a weighted graph
One-sided discrete terrain guarding and chordal graphs
Heuristic and metaheuristic methods for computing graph treewidth

This page was built for publication: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5634016)