Results 31 to 40 of about 1,490 (139)
How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs? [PDF]
, 2017 In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsky et al.
Bougeret, Marin, Sau, Ignasi
core +4 more sources
SAT-Encodings for Treecut Width and Treedepth [PDF]
, 2019 In this paper we propose, implement, and test the first practical decomposition algorithms for the width parameters treecut width and treedepth. These two parameters have recently gained a lot of attention in the theoretical research community as they offer the algorithmic advantage over treewidth by supporting so-called fixed-parameter algorithms for ...
Ganian, Robert +3 more
openaire +2 more sources
On space efficiency of algorithms working on structural decompositions of graphs [PDF]
, 2016 Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms.
Pilipczuk, Michał, Wrochna, Marcin
core +2 more sources
Sallow: a heuristic algorithm for treedepth decompositions
15th International Symposium on Parameterized and Exact Computation (IPEC 2020), 2020 We describe a heuristic algorithm for computing treedepth decompositions, submitted for the PACE 2020 challenge. It relies on a variety of greedy algorithms computing elimination orderings, as well as a Divide & Conquer approach on balanced cuts obtained using a from-scratch reimplementation of the 2016 FlowCutter algorithm by Hamann & Strasser
openaire +5 more sources
Comprehensive Parameter Sweep for Learning-based Detector on Traffic Lights [PDF]
, 2016 Determining the optimal parameters for a given detection algorithm is not straightforward and what ends up as the final values is mostly based on experience and heuristics.
Jensen, Morten Bornø +3 more
core +1 more source
Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, 2022 We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows: i) Binary CSP parameterized by the vertex cover number is $\mathrm{W}[3]$-complete.
Bodlaender, Hans L. +2 more
openaire +7 more sources
The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth
15th International Symposium on Parameterized and Exact Computation, IPEC 2020, 2020 This year’s Parameterized Algorithms and Computational Experiments challenge (PACE 2020) was devoted to the problem of computing the treedepth of a given graph. Altogether 51 participants from 20 teams, 12 countries and 3 continents submitted their implementations to the competition. In this report, we describe the setup of the challenge, the selection
Kowalik, Łukasz +5 more
openaire +4 more sources
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class [PDF]
, 2018 We develop a framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a scenario we expect is common when working with real-world networks) while still ...
Demaine, Erik D. +7 more
core +2 more sources
Design Analysis of Corridors-in-the-Sky [PDF]
, 2008 Corridors-in-the-sky or tubes is one of new concepts in dynamic airspace configuration. It accommodates high density traffic, which has similar trajectories. Less air traffic controllers workload is expected than classic airspaces, thus, corridors-in-the-
Daganzo C. F., Lighthill M. J.
core +2 more sources
Meta-Kernelization using Well-Structured Modulators [PDF]
, 2015 Kernelization investigates exact preprocessing algorithms with performance guarantees. The most prevalent type of parameters used in kernelization is the solution size for optimization problems; however, also structural parameters have been successfully ...
Eiben, Eduard +2 more
core +2 more sources