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

DOI10.1007/978-3-030-83508-8_41OpenAlexW3198094201MaRDI QIDQ832905

Arne Leitert

Publication date: 25 March 2022

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

Mathematics Subject Classification ID

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

Cites Work

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

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