scientific article; zbMATH DE number 7205214

DOI10.4230/LIPIcs.IPEC.2017.30zbMath1443.68220MaRDI QIDQ5111890

Nimrod Talmon, Holger Dell, Mathias Weller, Christian Komusiewicz

Publication date: 27 May 2020

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

zbMATH Keywords

treewidthcontestFPTminimum fill-inimplementation challenge

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10)

Related Items (26)

Efficient Knowledge Compilation Beyond Weighted Model Counting ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Computing Tree Decompositions ⋮ Experimental Analysis of Treewidth ⋮ An analysis of the parameterized complexity of periodic timetabling ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ The tree-width of C ⋮ Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ Exploiting Database Management Systems and Treewidth for Counting ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Solving projected model counting by utilizing treewidth and its limits ⋮ Computing partial hypergraphs of bounded width ⋮ Efficient interprocedural data-flow analysis using treedepth and treewidth ⋮ On integer linear programs for treewidth based on perfect elimination orderings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Practical Access to Dynamic Programming on Tree Decompositions ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. ⋮ Practical access to dynamic programming on tree decompositions ⋮ Unnamed Item ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth ⋮ Unnamed Item ⋮ DynASP2.5: Dynamic Programming on Tree Decompositions in Action ⋮ Proof complexity of symbolic QBF reasoning

Uses Software

• Regina
• dynASP
• ToTo
• Jdrasil

Cites Work

• Unnamed Item
• Unnamed Item
• \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
• Faster parameterized algorithms for \textsc{Minimum Fill-in}
• On the treewidth of toroidal grids
• Decomposition by clique separators
• All structured programs have small tree width and good register allocation
• Fixed-parameter tractability of graph modification problems for hereditary properties
• SAT-encodings for special treewidth and pathwidth
• A characterisation of rigid circuit graphs
• Answer set solving with bounded treewidth revisited
• Positive-instance driven dynamic programming for treewidth
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• A Faster Algorithm for Dominating Set Analyzed by the Potential Method
• Integrally Closed Domains, Minimal Polynomials, and Null Ideals of Matrices
• Exact Algorithms for Treewidth and Minimum Fill-In
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• Jdrasil: A Modular Library for Computing Tree Decompositions
• Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs
• DynASP2.5: Dynamic Programming on Tree Decompositions in Action
• Computing treewidth on the GPU
• Subexponential Parameterized Algorithm for Minimum Fill-In
• A Benders Approach to the Minimum Chordal Completion Problem

This page was built for publication: