Parameterized Complexity of Upper Edge Domination
Abstract
In this paper we study a maximization version of the classical Edge Dominating Set (EDS) problem, namely, the Upper EDS problem, in the realm of Parameterized Complexity. In this problem, given an undirected graph $G$, a positive integer $k$, the question is to check whether $G$ has a minimal edge dominating set of size at least $k$. We obtain the following results for Upper EDS. We prove that Upper EDS admits a kernel with at most $4k^2-2$ vertices. We also design a fixed-parameter tractable (FPT) algorithm for Upper EDS running in time $2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)}$.
Read the paper
Related studies
- The Matrisome: In Silico Definition and In Vivo Characterization by Proteomics of Normal and Tumor Extracellular Matrices
- The Escherichia coli MG1655 in silico metabolic genotype: Its definition, characteristics, and capabilities
- In silico pharmacology for drug discovery: methods for virtual ligand screening and profiling
- In silico prediction of splice-altering single nucleotide variants in the human genome
- In silico clinical trials: how computer simulation will transform the biomedical industry
- In silico optimization of a guava antimicrobial peptide enables combinatorial exploration for peptide design
Go deeper in Evidence Hub
Evidence Hub adds a study data sheet (design, sample size, evidence level, key numbers), an AI summary and a chat grounded in the paper's text.