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)
- 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
- A new algorithm for decomposition of graphical models
- An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
- A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
- Inference in belief networks: A procedural guide
- Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
- Enumeration of the perfect sequences of a chordal graph
- Uniform Constraint Satisfaction Problems and Database Theory
- Minimal fill in O(\(n^{2.69}\)) time
- Bayesian approaches for large biological networks
- Generating and characterizing the perfect elimination orderings of a chordal graph
- Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- The induced path function, monotonicity and betweenness
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Dynamic branching in qualitative constraint-based reasoning via counting local models
- On the maximum cardinality search lower bound for treewidth
- Unifying tree decompositions for reasoning in graphical models
- The recognition problem of graph search trees
- A note on odd/even cycles
- Collective singleton-based consistency for qualitative constraint networks: theory and practice
- Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
- Fast minimal triangulation algorithm using minimum degree criterion
- Path-based supports for hypergraphs
- On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
- Path-based supports for hypergraphs
- Twins in Subdivision Drawings of Hypergraphs
- Robustness to dependency in portfolio optimization using overlapping marginals
- Polarity of chordal graphs
- Efficient algorithms for network localization using cores of underlying graphs
- Existence of extensions and product extensions for discrete probability distributions
- Counting the number of independent sets in chordal graphs
- Interval graphs and related topics
- Chordality properties on graphs and minimal conceptual connections in semantic data models
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Semantic acyclicity on graph databases
- Graph connectivity and its augmentation: Applications of MA orderings
- A special case for subset interconnection designs
- Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
- Arboricity: an acyclic hypergraph decomposition problem motivated by database theory
- High dimensional posterior convergence rates for decomposable graphical models
- Studies on hypergraphs. I: Hyperforests
- Recognizing single-peaked preferences on a tree
- Blocks of hypergraphs. Applied to hypergraphs and outerplanarity
- A fully dynamic graph algorithm for recognizing interval graphs
- On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs
- LexBFS-orderings and powers of chordal graphs
- Algorithmic aspects of intersection graphs and representation hypergraphs
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- Computing partial hypergraphs of bounded width
- Prim-based support-graph preconditioners for min-cost flow problems
- Triangulation of Bayesian networks by retriangulation
- Title not available (Why is that?)
- Ninth and tenth order virial coefficients for hard spheres in \(D\) dimensions
- Recognizing different types of beta-cycles in a database scheme
- Laminar structure of ptolemaic graphs with applications
- An implementation of the iterative proportional fitting procedure by propagation trees.
- Hybrid backtracking bounded by tree-decomposition of constraint networks
- A note on lexicographic breadth first search for chordal graphs
- \(K_{1,3}\)-free and \(W_4\)-free graphs
- On the effective implementation of the iterative proportional fitting procedure
- Peakless functions on graphs
- A faster algorithm to recognize undirected path graphs
- Efficient local updates for undirected graphical models
- Distributed revision of composite beliefs
- 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
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)
