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

DOI10.4230/LIPICS.IPEC.2017.16MaRDI QIDQ5111875zbMATH OpenFDO

Authors David Eppstein, Denis Kurz

Publication date 27 May 2020

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

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)

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

Cites work

• scientific article; zbMATH DE number 53193 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 219268 (Why is no real title available?)
• scientific article; zbMATH DE number 7075879 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithmic meta theorems for circuit classes of constant and logarithmic depth
• Algorithms for finding k-best perfect matchings
• An algebraic theory of graph reduction
• An efficient algorithm for K shortest simple paths
• An optimal algorithm for selection in a min-heap
• Easy problems for tree-decomposable graphs
• Finding the K Shortest Loopless Paths in a Network
• Finding the k Shortest Paths
• Graph expressions and graph rewritings
• Making data structures persistent
• Monadic second-order evaluations on tree-decomposable graphs
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Solving the \(k\)-best traveling salesman problem
• Sparsification—a technique for speeding up dynamic graph algorithms
• Subcubic equivalences between path, matrix, and triangle problems
• The first order properties of products of algebraic systems
• Two Algorithms for Generating Weighted Spanning Trees in Order

Cited in

(2)

• Finding the \(k\) shortest simple paths: time and space trade-offs
• scientific article; zbMATH DE number 6862107 (Why is no real title available?)

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)