QP-2019-04

An efficient algorithm for testing $(k,\ell)$-sparsity when $\ell<0$

Csaba Király



Abstract

For two integers $k>0$ and $\ell$, a graph $G=(V,E)$ is called $(k,\ell)$-tight if $|E|=k|V|-\ell$ and $|E(X)|\leq k|X|-\ell$ for all $X\sbse V$ for which $k|X|-\ell\geq 0$. Lee and Streinu provided an algorithm for testing $(k,\ell)$-sparsity when $\ell\geq 0$. We show how to modify this algorithm for instances where $\ell<0$.


Bibtex entry:

@techreport{egresqp-19-04,
AUTHOR = {Kir{\'a}ly, Csaba},
TITLE = {An efficient algorithm for testing $(k,\ell)$-sparsity when $\ell<0$},
NOTE= {{\tt egres.elte.hu}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {QP-2019-04}
}


Last modification: 6.4.2021. Please email your comments to Tamás Király!