Listing all potential maximal cliques of a graph
From MaRDI portal
Publication:1605302
DOI10.1016/S0304-3975(01)00007-XzbMath1002.68104OpenAlexW1569612812WikidataQ127908699 ScholiaQ127908699MaRDI QIDQ1605302
Ioan Todinca, Vincent Bouchitte
Publication date: 15 July 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-46541-3_42
Related Items (39)
Minimal triangulations of graphs: a survey ⋮ Experimental Analysis of Treewidth ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators ⋮ Constructing Brambles ⋮ Treewidth computation and extremal combinatorics ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Graphs with polynomially many minimal separators ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Positive-instance driven dynamic programming for treewidth ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On the hardness of inclusion-wise minimal separators enumeration ⋮ Chordal embeddings of planar graphs ⋮ Unnamed Item ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ Faster parameterized algorithms for \textsc{Minimum Fill-in} ⋮ On treewidth approximations. ⋮ On the Maximum Weight Minimal Separator ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ On the complexity of computing treebreadth ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ Minimal separators in extended \(P_4\)-laden graphs ⋮ On probe permutation graphs ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ On a property of minimal triangulations ⋮ On the Number of Minimal Separators in Graphs ⋮ Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ On the maximum weight minimal separator ⋮ On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monadic second-order evaluations on tree-decomposable graphs
- Graph minors. III. Planar tree-width
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- All structured programs have small tree width and good register allocation
- Characterizations and algorithmic applications of chordal graph embeddings
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Dynamic algorithms for graphs of bounded treewidth
- Triangulated graphs and the elimination process
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Computing the Minimum Fill-In is NP-Complete
- The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Minimum Fill-in on Circle and Circular-Arc Graphs
- An algebraic theory of graph reduction
- Inferring Evolutionary History From DNA Sequences
- Treewidth of Circular-Arc Graphs
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Listing all Minimal Separators of a Graph
- Treewidth of Chordal Bipartite Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Approximating the bandwidth for asteroidal triple-free graphs
This page was built for publication: Listing all potential maximal cliques of a graph
