On finding optimal polytrees

DOI10.1016/j.tcs.2015.05.012zbMath1330.68223arXiv1208.1692OpenAlexW2563028924MaRDI QIDQ500966

Mathieu Liedloff, Mikko Koivisto, Sebastian Ordyniak, Stefan Szeider, Serge Gaspers

Publication date: 8 October 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

matroidsbranchingsparameterized complexitydirected acyclic graphspolytreesprobabilistic networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis ⋮ On finding optimal polytrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On finding optimal polytrees
• Exact exponential algorithms.
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Bayesian network classifiers
• Which problems have strongly exponential complexity?
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Learning Bayesian networks: The combination of knowledge and statistical data
• Parametrized complexity theory.
• Matroid Intersection
• Two algorithms for weighted matroid intersection
• A note on finding optimum branchings
• A weighted matroid intersection algorithm
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Finding optimum branchings
• Packing rooted directed cuts in a weighted directed graph
• Parameterized Complexity Results for Exact Bayesian Network Structure Learning
• Optimum branchings
• A simple derivation of edmonds' algorithm for optimum branchings