Parameterized Complexity of Equitable Coloring [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 A graph on $n$ vertices is equitably $k$-colorable if it is $k$-colorable and every color is used either $\left\lfloor n/k \right\rfloor$ or $\left\lceil n/k \right\rceil$ times.
Guilherme de C. M. Gomes +2 more
doaj +6 more sources
The parameterized space complexity of model-checking bounded variable first-order logic [PDF]
Logical Methods in Computer Science, 2019 The parameterized model-checking problem for a class of first-order sentences (queries) asks to decide whether a given sentence from the class holds true in a given relational structure (database); the parameter is the length of the sentence.
Yijia Chen +2 more
doaj +8 more sources
Parameterized Complexity Dichotomy for Steiner Multicut [PDF]
Journal of Computer and System Sciences, 2015 The Steiner Multicut problem asks, given an undirected graph G, terminals sets T1,...,Tt $\subseteq$ V(G) of size at most p, and an integer k, whether there is a set S of at most k edges or nodes s.t.
Karl Bringmann +3 more
core +16 more sources
Model-Checking Problems as a Basis for Parameterized Intractability [PDF]
Logical Methods in Computer Science, 2005 Most parameterized complexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem (the so-called weighted satisfiability problem). For example, Downey and Fellow's W-hierarchy is of this form.
Joerg Flum, Martin Grohe
doaj +4 more sources
On the parameterized complexity of the median and closest problems under some permutation metrics [PDF]
Algorithms for Molecular BiologyGenome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome ...
Luís Cunha, Ignasi Sau, Uéverton Souza
doaj +2 more sources
Parameterized Complexity of Secluded Connectivity Problems [PDF]
, 2015 The Secluded Path problem models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a selected path is its exposure, which is the total weight of vertices in ...
Fedor V. Fomin +3 more
openalex +7 more sources
Enhancing UAV Object Detection in Low-Light Conditions with ELS-YOLO: A Lightweight Model Based on Improved YOLOv11 [PDF]
SensorsDrone-view object detection models operating under low-light conditions face several challenges, such as object scale variations, high image noise, and limited computational resources.
Tianhang Weng, Xiaopeng Niu
doaj +2 more sources
Parameterized Complexity Results for a Model of Theory of Mind Based on Dynamic Epistemic Logic [PDF]
Electronic Proceedings in Theoretical Computer Science, 2016 In this paper we introduce a computational-level model of theory of mind (ToM) based on dynamic epistemic logic (DEL), and we analyze its computational complexity. The model is a special case of DEL model checking.
Iris van de Pol +2 more
doaj +3 more sources
Energy Distribution Optimization in Heterogeneous Networks with Min–Max and Local Constraints as Support of Ambient Intelligence [PDF]
SensorsIn recent years, ambient intelligence (AmI) has gained significant attention from both academia and industry. AmI seeks to create environments that automatically adapt to individuals’ needs, improving comfort and efficiency.
Alessandro Aloisio +3 more
doaj +2 more sources
New Algorithms for Mixed Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \textsc{Mixed Dominating Set}, resolving some open questions.
Louis Dublois +2 more
doaj +1 more source