Decomposition by clique separators

From MaRDI portal

Publication:1062072

Jump to:navigation, search

DOI10.1016/0012-365X(85)90051-2zbMath0572.05039WikidataQ56335617 ScholiaQ56335617MaRDI QIDQ1062072

Robert Endre Tarjan

Publication date: 1985

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

decomposition by clique separators

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Related Items

Characterizing atoms that result from decomposition by clique separators, Bounds for cell entries in contingency tables given marginal totals and decomposable graphs, Optimal decomposition by clique separators, Tree-decompositions with bags of small diameter, Complexity and Polynomially Solvable Special Cases of QUBO, All roads lead to Rome -- new search methods for the optimal triangulation problem, Fast Skew Partition Recognition, On CLIQUE Problem for Sparse Graphs of Large Dimension, Two classes of graphs in which some problems related to convexity are efficiently solvable, Unnamed Item, Applying clique-decomposition for computing Gromov hyperbolicity, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem, Helly EPT graphs on bounded degree trees: characterization and recognition, Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions, Colouring square-free graphs without long induced paths., Clique cutsets beyond chordal graphs, Completion to chordal distance-hereditary graphs: a quartic vertex-kernel, Minimal Disconnected Cuts in Planar Graphs, Combining decomposition approaches for the maximum weight stable set problem, Minimum weighted clique cover on claw‐free perfect graphs, Coloring rings, Two new characterizations of path graphs, Clique‐width: Harnessing the power of atoms, Parameterized complexity of path set packing, Solving larger maximum clique problems using parallel quantum annealing, Maximum max-k-clique subgraphs in cactus subtree graphs, Treewidth versus clique number. II: Tree-independence number, Finding induced paths of given parity in claw-free graphs, On new algorithmic techniques for the weighted vertex coloring problem, Unnamed Item, On the structure of (pan, even hole)‐free graphs, Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth, Matrix partitions of perfect graphs, Classes of perfect graphs, A Refined Analysis of Online Path Coloring in Trees, Revisiting Decomposition by Clique Separators, Unnamed Item, 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles, On asteroidal sets in chordal graphs, Solving Graph Problems via Potential Maximal Cliques, Graphs of Separability at Most Two: Structural Characterizations and Their Consequences, Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs, CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, Sums of Squares and Sparse Semidefinite Programming, The \(k\)-edge intersection graphs of paths in a tree, Representing edge intersection graphs of paths on degree 4 trees, A Class of Three‐Colorable Triangle‐Free Graphs, Recursive conditioning, The complexity of path coloring and call scheduling, Ninth and tenth order virial coefficients for hard spheres in \(D\) dimensions, Disjoint clique cutsets in graphs without long holes, The Maximum Independent Set Problem in Planar Graphs, The sandwich problem for cutsets: clique cutset, \(k\)-star cutset, Optimal pricing of capacitated networks, Finding cut-vertices in the square roots of a graph, Independent Sets in Classes Related to Chair-Free Graphs, Graph partitions with prescribed patterns, Fractional path coloring in bounded degree trees with applications, On \(H\)-topological intersection graphs, Join colourings of chordal graphs, Decomposability of abstract and path-induced convexities in hypergraphs, On Injective Colourings of Chordal Graphs, A tight approximation algorithm for the cluster vertex deletion problem, Junction trees of general graphs, Strong cliques in diamond-free graphs, Unnamed Item, Maximum independent sets in subcubic graphs: new results, A tight approximation algorithm for the cluster vertex deletion problem, Finding the minimal set for collapsible graphical models, On Computing the Gromov Hyperbolicity, Attachment centrality: measure for connectivity in networks, Evaluating Datalog via tree automata and cycluits, On Distance-3 Matchings and Induced Matchings, Colouring square-free graphs without long induced paths, Counting Weighted Independent Sets beyond the Permanent, Clique roots of K4-free chordal graphs, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds, Matrix Partitions with Finitely Many Obstructions, Safe separators for treewidth, Minimal fill in O(\(n^{2.69}\)) time, Intersection graphs of paths in a tree, Complexity aspects of the triangle path convexity, The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable, Graphs of edge-intersecting and non-splitting paths, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, Representing a concept lattice by a graph, Maximum weight independent sets and cliques in intersection graphs of filaments, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Weighted independent sets in classes of \(P_6\)-free graphs, On independent vertex sets in subclasses of apple-free graphs, Exploring gene causal interactions using an enhanced constraint-based method, Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I, Intersection graphs of vertex disjoint paths in a tree, Cuts, matrix completions and graph rigidity, Complexity of coloring graphs without paths and cycles, Maximum weight independent sets in classes related to claw-free graphs, Colouring perfect graphs with bounded clique number, On chordal and perfect plane near-triangulations, On decomposability of multilinear sets, An introduction to clique minimal separator decomposition, Computing a clique tree with the algorithm maximal label search, New applications of clique separator decomposition for the maximum weight stable set problem, Simplicial decompositions of graphs: A survey of applications, Triangulating graphs without asteroidal triples, The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs, The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring, Obstructions to partitions of chordal graphs, On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem, A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree, Separability generalizes Dirac's theorem, Triangulating multitolerance graphs, Structure and algorithms for (cap, even hole)-free graphs, A coloring algorithm for \(4 K_1\)-free line graphs, A new characterization of unichord-free graphs, 3-colouring AT-free graphs in polynomial time, Organizing the atoms of the clique separator decomposition into an atom tree, Combinatorial problems on \(H\)-graphs, On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent, On stable cutsets in line graphs, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, The maximum infection time in the geodesic and monophonic convexities, Graphs of separability at most 2, Weighted independent sets in a subclass of \(P_6\)-free graphs, On easy and hard hereditary classes of graphs with respect to the independent set problem, On graphs with no induced subdivision of \(K_4\), Colouring, constraint satisfaction, and complexity, On treewidth approximations., Decomposition by maxclique separators, The (theta, wheel)-free graphs. IV: Induced paths and cycles, Representations of graphs and networks (coding, layouts and embeddings), Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs, Some properties of graph centroids, Trees of tangles in abstract separation systems, On stable cutsets in claw-free graphs and planar graphs, Inapproximability and approximability of minimal tree routing and coloring, On the parameterized complexity of finding separators with non-hereditary properties, Asymptotic bounds on the equilateral dimension of hypercubes, Walrasian equilibrium: Hardness, approximations and tractable instances, A note on lexicographic breadth first search for chordal graphs, On the choosability of claw-free perfect graphs, Two complexity results for the vertex coloring problem, Solving some NP-complete problems using split decomposition, A linear algorithm for the group path problem on chordal graphs, On the structure of (even hole, kite)-free graphs, A new algorithm for decomposition of graphical models, Minimum fill-in of sparse graphs: kernelization and approximation, Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree, Approximation of knapsack problems with conflict and forcing graphs, Conversion of coloring algorithms into maximum weight independent set algorithms, A divide-and-conquer algorithm for generating Markov bases of multi-way tables, Maximum weight independent sets in hole- and dart-free graphs, On distance-3 matchings and induced matchings, Dichotomy for tree-structured trigraph list homomorphism problems, Complexity results related to monophonic convexity, Perfect graphs with polynomially computable kernels, Maximum colorful independent sets in vertex-colored graphs, Graphs without large apples and the maximum weight independent set problem, The complexity of generalized clique covering, The intersection of two vertex coloring problems, On the maximum cardinality cut problem in proper interval graphs and related graph classes, Resource allocation in bounded degree trees, Maximum weight independent sets in hole- and co-chair-free graphs, Decomposition of a hypergraph by partial-edge separators, Clique or hole in claw-free graphs, Structural submodularity and tangles in abstract separation systems, Some results on the Gaussian Markov random field construction problem based on the use of invariant subgraphs, On coloring a class of claw-free and hole-twin-free graphs, The edge intersection graphs of paths in a tree, A description of claw-free perfect graphs, Edge and vertex intersection of paths in a tree, Interval graphs and related topics, Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey, Algorithms for maximum weight induced paths, Recognition algorithm for intersection graphs of edge disjoint paths in a tree, An implementation of the iterative proportional fitting procedure by propagation trees., Routing and path multicoloring, Strong cliques and equistability of EPT graphs, List matrix partitions of chordal graphs

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1062072&oldid=13081055"