scientific article; zbMATH DE number 7205200

DOI10.4230/LIPIcs.IPEC.2017.16zbMath1443.68127arXiv1703.02784MaRDI QIDQ5111875

Denis Kurz, David Eppstein

Publication date: 27 May 2020

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

graph algorithmmonadic second-order logictreewidth\(k\)-best solution

Mathematics Subject Classification ID

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

Cites Work

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