On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay

DOI10.1007/978-3-540-95891-8_19MaRDI QIDQ3599072zbMATH OpenOpenAlexFDO

Authors Taishin Daigo, Kouichi Hirata

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-95891-8_19

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A polynomial delay algorithm for generating connected induced subgraphs of a given cardinality
• New polynomial delay bounds for maximal subgraph enumeration by proximity search
• A polynomial delay algorithm for enumerating 2-edge-connected induced subgraphs
• The Complexity of Acyclic Subhypergraph Problems
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• Polynomial-delay and polynomial-space enumeration of large maximal matchings
• Tight Bounds for the Maximum Acyclic Subgraph Problem
• Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay
• Fundamentals of Computation Theory

Cites work

• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Conjunctive query containment revisited
• Degrees of acyclicity for hypergraphs and relational database schemes
• Finding All Spanning Trees of Directed and Undirected Graphs
• Frequent Hypergraph Mining
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On generating all maximal independent sets
• On hypergraph acyclicity and graph chordality
• On the Desirability of Acyclic Database Schemes
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The complexity of acyclic conjunctive queries

Cited in

(3)

• Listing acyclic subgraphs and subgraphs of bounded girth in directed graphs
• Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay
• Fundamentals of Computation Theory

This page was built for publication: On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay

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