k-best solutions of MSO problems on tree-decomposable graphs

DOI10.4230/LIPICS.IPEC.2017.16zbMATH Open1443.68127arXiv1703.02784MaRDI QIDQ5111875FDOQ5111875

Authors: David Eppstein, Denis Kurz 

Publication date: 27 May 2020

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

Recommendations

• scientific article; zbMATH DE number 7075879
• scientific article; zbMATH DE number 6862107
• On the \(K\) shortest path trees problem
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• scientific article; zbMATH DE number 4081531

zbMATH Keywords

treewidthgraph algorithmmonadic second-order logic\(k\)-best solution

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Logic in computer science (03B70)

Cites Work

• Finding the k Shortest Paths
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Easy problems for tree-decomposable graphs
• Algorithms for finding k-best perfect matchings
• Title not available (Why is that?)
• Finding the K Shortest Loopless Paths in a Network
• Making data structures persistent
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Sparsification—a technique for speeding up dynamic graph algorithms
• Title not available (Why is that?)
• Two Algorithms for Generating Weighted Spanning Trees in Order
• Monadic second-order evaluations on tree-decomposable graphs
• The first order properties of products of algebraic systems
• An efficient algorithm for K shortest simple paths
• An optimal algorithm for selection in a min-heap
• Title not available (Why is that?)
• Solving the \(k\)-best traveling salesman problem
• An algebraic theory of graph reduction
• Algorithmic meta theorems for circuit classes of constant and logarithmic depth
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Graph expressions and graph rewritings
• Title not available (Why is that?)

Cited In (2)

• Title not available (Why is that?)
• Finding the \(k\) shortest simple paths: time and space trade-offs

This page was built for publication: \(k\)-best solutions of MSO problems on tree-decomposable graphs

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