Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
From MaRDI portal
Publication:3335007
DOI10.1137/0213035zbMATH Open0545.68062DBLPjournals/siamcomp/TarjanY84OpenAlexW1991477862WikidataQ90315968 ScholiaQ90315968MaRDI QIDQ3335007FDOQ3335007
Authors: Mihalis Yannakakis, Robert E. Tarjan 
Publication date: 1984
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0213035
Recommendations
- Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- On hypergraph acyclicity and graph chordality
- Degrees of acyclicity for hypergraphs and relational database schemes
- Maximal chordal subgraphs
- Efficient Parallel Algorithms for Chordal Graphs
graph algorithmgraph searchChordal graphsacyclic hypergraphssparse Gaussian eliminationacyclic data base scheme
Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Information storage and retrieval of data (68P20) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65)
Cited In (only showing first 100 items - show all)
- Polynomial kernels for proper interval completion and related problems
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- Finding clubs in graph classes
- Title not available (Why is that?)
- Probability propagation
- Detecting fixed patterns in chordal graphs in polynomial time
- The maximum clique problem
- Organizing the atoms of the clique separator decomposition into an atom tree
- Equivalence between hypergraph convexities
- Some aspects of the semi-perfect elimination
- Treewidth computations. II. Lower bounds
- A general label search to investigate classical graph search algorithms
- Satisfiability of acyclic and almost acyclic CNF formulas
- \(k\)-NLC graphs and polynomial algorithms
- Linear time algorithms for dominating pairs in asteroidal triple-free graphs
- Finding large holes
- Diameter determination on restricted graph families
- Conjunctive query containment revisited
- On the power of graph searching for cocomparability graphs
- Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs
- New lower bounds for bin packing problems with conflicts
- Discovering a junction tree behind a Markov network by a greedy algorithm
- Hypertree decompositions and tractable queries
- A linear time recognition algorithm for proper interval graphs
- Fast Bayes and the dynamic junction forest
- Canonical and monophonic convexities in hypergraphs
- Satisfiability of acyclic and almost acyclic CNF formulas. II
- On the semi-perfect elimination
- Temporal constraint networks
- On hypergraph acyclicity and graph chordality
- A generalization of chordal graphs and the maximum clique problem
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- A fast algorithm for query optimization in universal-relation databases
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Decomposition of structural learning about directed acyclic graphs
- Retracts of products of chordal graphs
- Restricted triangulation on circulant graphs
- Network-based heuristics for constraint-satisfaction problems
- A complete axiomatization of full acyclic join dependencies
- The recognition of geodetically connected graphs
- Separability generalizes Dirac's theorem
- Minimal triangulations of graphs: a survey
- A practical algorithm for making filled graphs minimal
- The graph formulation of the union-closed sets conjecture
- Decomposing constraint satisfaction problems using database techniques
- Graph extremities defined by search algorithms
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- MCMC model determination for discrete graphical models
- Some results on the target set selection problem
- A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
- Complexity classification of some edge modification problems
- A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Recognizing graph search trees
- The clique-separator graph for chordal graphs
- On 3-Steiner simplicial orderings
- Maximal chordal subgraphs
- The forbidden subgraph characterization of directed vertex graphs
- Tree decompositions of graphs: saving memory in dynamic programming
- Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
- Treewidth computations. I: Upper bounds
- A backward selection procedure for approximating a discrete probability distribution by decomposable models
- Perspectives on the theory and practice of belief functions
- Finding minimum height elimination trees for interval graphs in polynomial time
- On computing minimal models
- Moplex orderings generated by the LexDFs algorithm
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Partition search for non-binary constraint satisfaction
- Tree clustering for constraint networks
- Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones
- A review of tree convex sets test
- Vertex ordering characterizations of graphs of bounded asteroidal number
- Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
- Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
- Optimal decomposition by clique separators
- Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts
- Sequences of regressions and their independences
- Computing cooperative solution concepts in coalitional skill games
- Clique tree generalization and new subclasses of chordal graphs
- Contracting chordal graphs and bipartite graphs to paths and trees
- Detecting induced subgraphs
- Chordless paths through three vertices
- Static and dynamic source locations in undirected networks
- Perfect elimination orderings of chordal powers of graphs
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- Characterizing path graphs by forbidden induced subgraphs
- \(r\)-dominating cliques in graphs with hypertree structure
- Inclusion/exclusion meets measure and conquer
- Revisiting Decomposition by Clique Separators
- A note on minimal d-separation trees for structural learning
- Dynamic Branching in Qualitative Constraint Networks via Counting Local Models
- Computing the maximum-entropy extension of given discrete probability distributions
- A logic-based analysis of Dempster-Shafer theory
- Cycle structure of edge labelled graphs
- Heuristic and metaheuristic methods for computing graph treewidth
- Chordal graph recognition is in NC
- Structural conditions for cycle completable graphs
- Minimal vertex separators of chordal graphs
- Linear-time algorithms for tree root problems
This page was built for publication: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3335007)
