Computing the union join and subset graph of acyclic hypergraphs in subquadratic time

DOI10.1007/978-3-030-83508-8_41MaRDI QIDQ832905zbMATH OpenOpenAlexFDO

Authors Arne Leitert

Publication date 25 March 2022

Full work available at URL https://arxiv.org/abs/2104.06636

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Cites work

• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Chordal graphs and their clique graphs
• Computing the subset partial order for dense families of sets
• Degrees of acyclicity for hypergraphs and relational database schemes
• Dually Chordal Graphs
• Into the square: on the complexity of some quadratic-time solvable problems
• Laminar structure of ptolemaic graphs with applications
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• On Computing the Subset Graph of a Collection of Sets
• On the Desirability of Acyclic Database Schemes
• Opportunistic algorithms for eliminating supersets
• Optimal decomposition by clique separators
• Reduced clique graphs of chordal graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Spanners for bounded tree-length graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Three Partition Refinement Algorithms
• Tree-structured graphs

This page was built for publication: Computing the union join and subset graph of acyclic hypergraphs in subquadratic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832905)