The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.

DOI10.4230/LIPICS.IPEC.2020.37MaRDI QIDQ6089686zbMATH OpenOpenAlexFDO

Authors Łukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, Piotr Wygocki

Publication date 13 November 2023

Full work available at URL https://doi.org/10.4230/LIPIcs.IPEC.2020.37

zbMATH Keywords

contestFPTimplementation challengecomputing treedepth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• scientific article; zbMATH DE number 7525471 (Why is no real title available?)
• scientific article; zbMATH DE number 7764118 (Why is no real title available?)
• scientific article; zbMATH DE number 7764119 (Why is no real title available?)
• scientific article; zbMATH DE number 7764120 (Why is no real title available?)
• scientific article; zbMATH DE number 7764121 (Why is no real title available?)
• scientific article; zbMATH DE number 7764122 (Why is no real title available?)
• scientific article; zbMATH DE number 7764125 (Why is no real title available?)
• scientific article; zbMATH DE number 7764126 (Why is no real title available?)
• scientific article; zbMATH DE number 7764127 (Why is no real title available?)
• A faster parameterized algorithm for treedepth
• A polynomial excluded-minor approximation of treedepth
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Graph bisection with Pareto optimization
• Graph minors. II. Algorithmic aspects of tree-width
• Nested Dissection of a Regular Finite Element Mesh
• On low tree-depth decompositions
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• Optimal node ranking of tree in linear time
• PACE Solver Description: Finding Elimination Trees Using ExTREEm - a Heuristic Solver for the Treedepth Decomposition Problem
• PACE Solver Description: Tree Depth with FlowCutter
• Positive-instance driven dynamic programming for treewidth
• Positive-instance driven dynamic programming for treewidth
• SAT-encodings for treecut width and treedepth
• Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
• Sparsity. Graphs, structures, and algorithms
• The Evolution of the Minimum Degree Ordering Algorithm
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
• The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)
• Tree-depth, subgraph coloring and homomorphism bounds
• Treedepth Parameterized by Vertex Cover Number.

Cited in

(8)

• On the size of minimal separators for treedepth decomposition
• The PACE 2022 parameterized algorithms and computational experiments challenge: directed feedback vertex set
• Computing treedepth in polynomial space and linear FPT time
• Turbocharging heuristics for weak coloring numbers
• Efficient interprocedural data-flow analysis using treedepth and treewidth
• The PACE 2024 parameterized algorithms and computational experiments challenge: one-sided crossing minimization
• Closure property of contraction-depth of matroids
• PACE solver description: the PACE 2023 parameterized algorithms and computational experiments challenge: twinwidth

This page was built for publication: The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.

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