The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties
N Fischer, M Künnemann, M Redzic - Proceedings of the 2024 Annual ACM …, 2024 - SIAM
We revisit the classic k-Dominating Set problem. Besides its importance as perhaps the most
natural W [2]-complete problem, it is among the first problems for which a tight nk-o (1) …
natural W [2]-complete problem, it is among the first problems for which a tight nk-o (1) …
Optimized design refactoring (ODR): a generic framework for automated search-based refactoring to optimize object-oriented software architectures
T Houichime, Y El Amrani - Automated Software Engineering, 2024 - Springer
Software design optimization (SDO) demands advanced abstract reasoning to define
optimal design components' structure and interactions. Modeling tools such as UML and …
optimal design components' structure and interactions. Modeling tools such as UML and …
A structural investigation of the approximability of polynomial-time problems
We initiate the systematic study of a recently introduced polynomial-time analogue of
MaxSNP, which includes a large number of well-studied problems (including Nearest and …
MaxSNP, which includes a large number of well-studied problems (including Nearest and …
Algorithms for sparse convolution and sublinear edit distance
N Fischer - 2023 - publikationen.sulb.uni-saarland.de
In this PhD thesis on fine-grained algorithm design and complexity, we investigate output-
sensitive and sublinear-time algorithms for two important problems.(1) Sparse Convolution …
sensitive and sublinear-time algorithms for two important problems.(1) Sparse Convolution …
Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization
T Yamakami - arXiv preprint arXiv:2410.04117, 2024 - arxiv.org
In a discussion on the computational complexity of``parameterized''NL (nondeterministic
logarithmic-space complexity class), Syntactic NL or succinctly SNL was first introduced in …
logarithmic-space complexity class), Syntactic NL or succinctly SNL was first introduced in …
Logical Expressibility of Syntactic NL for Complementarity and Maximization
T Yamakami - … Workshop on Logic, Language, Information, and …, 2024 - Springer
In a discussion on the computational complexity of “parameterized” NL (nondeterministic
logarithmic-space complexity class), Syntactic NL or succinctly SNL was first introduced in …
logarithmic-space complexity class), Syntactic NL or succinctly SNL was first introduced in …
Faculty of Engineering, University of Fukui, 3-9-1 Bunkyo, Fukui 910-8507, Japan tomoyukiyamakami@ gmail. com
T Yamakami - Intelligent Computing: Proceedings of the 2024 … - books.google.com
We study the computational complexity of counting constraint satisfaction problems (# CSPs)
whose constraints assign complex numbers to Boolean inputs when the corresponding …
whose constraints assign complex numbers to Boolean inputs when the corresponding …