Hypergraph traversal revisited: Cost measures and dynamic algorithms
A directed hypergraph is defined in this paper by a set of nodes and a set of directed hyperedges, where each hyperedge connects a set of source nodes to a target node. Also the notion of hyperpath is defined---it is a generalization of the notion of path for directed graphs. There are several different notions that all generalize the notion of ``length of a path in a directed graph. For several of these ``length-notions for directed hypergraphs, the problem of finding an optimal hyperpath is NP-complete. In this paper, a general view is taken to these notions and a study is made to the intrinsic complexity of finding optimal hyperpaths under several measures of optimality. It is shown that all notions that are cycle unbounded or 1-cycle-convergent have polynomial time algorithms. The notions of cycle unbounded or 1-cycle-convergent basically say that there is an optimal hyperpath without a generalized cycle or with at most one generalized cycle. For the entire collection see [Zbl 0895.00049].
- Linear connectivity problems in directed hypergraphs
- Shortest path algorithms for functional environments
- Partially dynamic maintenance of minimum weight hyperpaths
- Directed hypergraphs and applications
- Optimal directed hypergraph traversal with ant-colony optimisation
- Finding hypernetworks in directed hypergraphs
- Finding the \(K\) best policies in a finite-horizon Markov decision process
- Structure theorems for optimum hyperpaths in directed hypergraphs
- Sequence hypergraphs
- scientific article; zbMATH DE number 2044509 (Why is no real title available?)
- Association Rules Network: Definition and Applications
- Directed hypergraphs: introduction and fundamental algorithms -- a survey
- Finding the shortest path for a hypergraph
- Finding (s,d)-hypernetworks in F-hypergraphs is NP-hard
- Sequence Hypergraphs: Paths, Flows, and Cuts
- scientific article; zbMATH DE number 7716306 (Why is no real title available?)
- Dynamic maintenance of directed hypergraphs
This page was built for publication: Hypergraph traversal revisited: Cost measures and dynamic algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218092)
