Decomposition by clique separators
From MaRDI portal
Publication:1062072
DOI10.1016/0012-365X(85)90051-2zbMATH Open0572.05039DBLPjournals/dm/Tarjan85WikidataQ56335617 ScholiaQ56335617MaRDI QIDQ1062072FDOQ1062072
Authors: Robert E. Tarjan 
Publication date: 1985
Published in: Discrete Mathematics (Search for Journal in Brave)
Recommendations
Cites Work
- Title not available (Why is that?)
- Depth-First Search and Linear Graph Algorithms
- Edge and vertex intersection of paths in a tree
- Incidence matrices and interval graphs
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- Maximum matching and a polyhedron with 0,1-vertices
- On rigid circuit graphs
- The edge intersection graphs of paths in a tree
- A Separator Theorem for Planar Graphs
- Title not available (Why is that?)
- Triangulated graphs and the elimination process
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Computing the Minimum Fill-In is NP-Complete
- Dividing a Graph into Triconnected Components
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Theorem on Coloring the Lines of a Network
- Algorithms on clique separable graphs
- Title not available (Why is that?)
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- An algorithm for finding clique cut-sets
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- Linear-time computability of combinatorial problems on series-parallel graphs
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- Maximum weight independent sets in hole- and co-chair-free graphs
- Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
- Matrix partitions of perfect graphs
- On independent vertex sets in subclasses of apple-free graphs
- Strong cliques and equistability of EPT graphs
- On graphs with no induced subdivision of \(K_4\)
- Graph partitions with prescribed patterns
- Organizing the atoms of the clique separator decomposition into an atom tree
- Title not available (Why is that?)
- Graphs without large apples and the maximum weight independent set problem
- The Maximum Independent Set Problem in Planar Graphs
- Graphs of separability at most 2
- Colouring, constraint satisfaction, and complexity
- Strong cliques in diamond-free graphs
- The complexity of path coloring and call scheduling
- The edge intersection graphs of paths in a tree
- Complexity aspects of the triangle path convexity
- Minimal fill in O(\(n^{2.69}\)) time
- Safe separators for treewidth
- Edge and vertex intersection of paths in a tree
- Intersection graphs of paths in a tree
- Graphs of edge-intersecting and non-splitting paths
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Maximum independent sets in subcubic graphs: new results
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On the choosability of claw-free perfect graphs
- Maximum weight independent sets and cliques in intersection graphs of filaments
- Weighted independent sets in classes of \(P_6\)-free graphs
- Separability generalizes Dirac's theorem
- On stable cutsets in line graphs
- Triangulating graphs without asteroidal triples
- Maximum weight independent sets in classes related to claw-free graphs
- On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Decomposition of a hypergraph by partial-edge separators
- Complexity results related to monophonic convexity
- An introduction to clique minimal separator decomposition
- Maximum weight independent sets in hole- and dart-free graphs
- 3-colouring AT-free graphs in polynomial time
- Exploring gene causal interactions using an enhanced constraint-based method
- New applications of clique separator decomposition for the maximum weight stable set problem
- A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
- Graphs of separability at most two: structural characterizations and their consequences
- Weighted independent sets in a subclass of \(P_6\)-free graphs
- A Refined Analysis of Online Path Coloring in Trees
- Solving some NP-complete problems using split decomposition
- Resource allocation in bounded degree trees
- The complexity of generalized clique covering
- Decomposition by maxclique separators
- A description of claw-free perfect graphs
- Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I
- Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
- Characterizing atoms that result from decomposition by clique separators
- Representing edge intersection graphs of paths on degree 4 trees
- Algorithms for maximum weight induced paths
- Triangulating multitolerance graphs
- Title not available (Why is that?)
- Simplicial decompositions of graphs: A survey of applications
- Fast Skew Partition Recognition
- Complexity of coloring graphs without paths and cycles
- Colouring perfect graphs with bounded clique number
- Optimal decomposition by clique separators
- On treewidth approximations.
- A divide-and-conquer algorithm for generating Markov bases of multi-way tables
- On the maximum cardinality cut problem in proper interval graphs and related graph classes
- On distance-3 matchings and induced matchings
- Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
- 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles
- The \(k\)-edge intersection graphs of paths in a tree
- Asymptotic bounds on the equilateral dimension of hypercubes
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- A class of three-colorable triangle-free graphs
- Obstructions to partitions of chordal graphs
- On computing the Gromov hyperbolicity
- Revisiting Decomposition by Clique Separators
- On Injective Colourings of Chordal Graphs
- Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
- Recursive conditioning
- List matrix partitions of chordal graphs
- On stable cutsets in claw-free graphs and planar graphs
- An implementation of the iterative proportional fitting procedure by propagation trees.
- Complexity and Polynomially Solvable Special Cases of QUBO
- On coloring a class of claw-free and hole-twin-free graphs
- Finding induced paths of given parity in claw-free graphs
- A note on lexicographic breadth first search for chordal graphs
- Tree-decompositions with bags of small diameter
- Title not available (Why is that?)
- Representations of graphs and networks (coding, layouts and embeddings)
- Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions
- Solving Graph Problems via Potential Maximal Cliques
- Approximation of knapsack problems with conflict and forcing graphs
- A linear algorithm for the group path problem on chordal graphs
- The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
- Solving larger maximum clique problems using parallel quantum annealing
- Bisimplicial separators
- A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree
- Join colourings of chordal graphs
- Routing and path multicoloring
- Structural submodularity and tangles in abstract separation systems
This page was built for publication: Decomposition by clique separators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1062072)
