Decomposition by clique separators
From MaRDI portal
Publication:1062072
DOI10.1016/0012-365X(85)90051-2zbMath0572.05039DBLPjournals/dm/Tarjan85WikidataQ56335617 ScholiaQ56335617MaRDI QIDQ1062072
Publication date: 1985
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
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 6 ‐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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On rigid circuit graphs
- The edge intersection graphs of paths in a tree
- Edge and vertex intersection of paths in a tree
- An algorithm for finding clique cut-sets
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- Algorithms on clique separable graphs
- Incidence matrices and interval graphs
- Triangulated graphs and the elimination process
- A Separator Theorem for Planar Graphs
- The NP-Completeness of Edge-Coloring
- Linear-time computability of combinatorial problems on series-parallel graphs
- Computing the Minimum Fill-In is NP-Complete
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Algorithmic Aspects of Vertex Elimination on Graphs
- Dividing a Graph into Triconnected Components
- Maximum matching and a polyhedron with 0,1-vertices
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Depth-First Search and Linear Graph Algorithms
- A Theorem on Coloring the Lines of a Network
This page was built for publication: Decomposition by clique separators
