Source author record

Hongyu Liang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Data Structures and Algorithms math.CO Databases Networking and Internet Architecture

Catalog footprint

Research overview

7works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Optimal Rendezvous Strategies for Different Environments in Cognitive Radio Networks

In Cognitive Radio Networks (CRNs), the secondary users (SUs) are allowed to access the licensed channels opportunistically. A fundamental and essential operation for SUs is to establish communication through choosing a common channel at the same time slot, which is referred to as rendezvous problem. In this paper, we study strategies to achieve fast rendezvous for two secondary users. The channel availability for secondary nodes is subject to temporal and spatial variation. Moreover, in a distributed system, one user is oblivious of the other user's channel status. Therefore, a fast rendezvous is not trivial. Recently, a number of rendezvous strategies have been proposed for different system settings, but rarely have they taken the temporal variation of the channels into account. In this work, we first derive a time-adaptive strategy with optimal expected time-to-rendezvous (TTR) for synchronous systems in stable environments, where channel availability is assumed to be static over time. Next, in dynamic environments, which better represent temporally dynamic channel availability in CRNs, we first derive optimal strategies for two special cases, and then prove that our strategy is still asymptotically optimal in general dynamic cases. Numerous simulations are conducted to demonstrate the performance of our strategies, and validate the theoretical analysis. The impacts of different parameters on the TTR are also investigated, such as the number of channels, the channel open possibilities, the extent of the environment being dynamic, and the existence of an intruder.

preprint2013arXiv

Matroid and Knapsack Center Problems

In the classic $k$ -center problem, we are given a metric graph, and the objective is to open $k$ nodes as centers such that the maximum distance from any vertex to its closest center is minimized. In this paper, we consider two important generalizations of $k$ -center, the matroid center problem and the knapsack center problem. Both problems are motivated by recent content distribution network applications. Our contributions can be summarized as follows: 1. We consider the matroid center problem in which the centers are required to form an independent set of a given matroid. We show this problem is NP-hard even on a line. We present a 3-approximation algorithm for the problem on general metrics. We also consider the outlier version of the problem where a given number of vertices can be excluded as the outliers from the solution. We present a 7-approximation for the outlier version. 2. We consider the (multi-)knapsack center problem in which the centers are required to satisfy one (or more) knapsack constraint(s). It is known that the knapsack center problem with a single knapsack constraint admits a 3-approximation. However, when there are at least two knapsack constraints, we show this problem is not approximable at all. To complement the hardness result, we present a polynomial time algorithm that gives a 3-approximate solution such that one knapsack constraint is satisfied and the others may be violated by at most a factor of $1+ε$ . We also obtain a 3-approximation for the outlier version that may violate the knapsack constraint by $1+ε$ .

preprint2013arXiv

On the Complexity of $t$ -Closeness Anonymization and Related Problems

An important issue in releasing individual data is to protect the sensitive information from being leaked and maliciously utilized. Famous privacy preserving principles that aim to ensure both data privacy and data integrity, such as $k$ -anonymity and $l$ -diversity, have been extensively studied both theoretically and empirically. Nonetheless, these widely-adopted principles are still insufficient to prevent attribute disclosure if the attacker has partial knowledge about the overall sensitive data distribution. The $t$ -closeness principle has been proposed to fix this, which also has the benefit of supporting numerical sensitive attributes. However, in contrast to $k$ -anonymity and $l$ -diversity, the theoretical aspect of $t$ -closeness has not been well investigated. We initiate the first systematic theoretical study on the $t$ -closeness principle under the commonly-used attribute suppression model. We prove that for every constant $t$ such that $0\leq t<1$ , it is NP-hard to find an optimal $t$ -closeness generalization of a given table. The proof consists of several reductions each of which works for different values of $t$ , which together cover the full range. To complement this negative result, we also provide exact and fixed-parameter algorithms. Finally, we answer some open questions regarding the complexity of $k$ -anonymity and $l$ -diversity left in the literature.

preprint2013arXiv

On the Complexity of Connectivity in Cognitive Radio Networks Through Spectrum Assignment

Cognitive Radio Networks (CRNs) are considered as a promising solution to the spectrum shortage problem in wireless communication. In this paper, we initiate the first systematic study on the algorithmic complexity of the connectivity problem in CRNs through spectrum assignments. We model the network of secondary users (SUs) as a potential graph, where two nodes having an edge between them are connected as long as they choose a common available channel. In the general case, where the potential graph is arbitrary and the SUs may have different number of antennae, we prove that it is NP-complete to determine whether the network is connectable even if there are only two channels. For the special case where the number of channels is constant and all the SUs have the same number of antennae, which is more than one but less than the number of channels, the problem is also NP-complete. For the special cases in which the potential graph is complete, a tree, or a graph with bounded treewidth, we prove the problem is NP-complete and fixed-parameter tractable (FPT) when parameterized by the number of channels. Exact algorithms are also derived to determine the connectability of a given cognitive radio network.

preprint2012arXiv

On Rainbow- $k$ -Connectivity of Random Graphs

A path in an edge-colored graph is called a \emph{rainbow path} if all edges on it have pairwise distinct colors. For $k\geq 1$ , the \emph{rainbow- $k$ -connectivity} of a graph $G$ , denoted $rc_k(G)$ , is the minimum number of colors required to color the edges of $G$ in such a way that every two distinct vertices are connected by at least $k$ internally disjoint rainbow paths. In this paper, we study rainbow- $k$ -connectivity in the setting of random graphs. We show that for every fixed integer $d\geq 2$ and every $k\leq O(\log n)$ , $p=\frac{(\log n)^{1/d}}{n^{(d-1)/d}}$ is a sharp threshold function for the property $rc_k(G(n,p))\leq d$ . This substantially generalizes a result due to Caro et al., stating that $p=\sqrt{\frac{\log n}{n}}$ is a sharp threshold function for the property $rc_1(G(n,p))\leq 2$ . As a by-product, we obtain a polynomial-time algorithm that makes $G(n,p)$ rainbow- $k$ -connected using at most one more than the optimal number of colors with probability $1-o(1)$ , for all $k\leq O(\log n)$ and $p=n^{-ε(1\pm o(1))}$ for some constant $ε\in[0,1)$ .

preprint2012arXiv

On the Signed (Total) $k$ -Domination Number of a Graph

Let $k$ be a positive integer and $G=(V,E)$ be a graph of minimum degree at least $k-1$ . A function $f:V\rightarrow \{-1,1\}$ is called a \emph{signed $k$ -dominating function} of $G$ if $\sum_{u\in N_G[v]}f(u)\geq k$ for all $v\in V$ . The \emph{signed $k$ -domination number} of $G$ is the minimum value of $\sum_{v\in V}f(v)$ taken over all signed $k$ -dominating functions of $G$ . The \emph{signed total $k$ -dominating function} and \emph{signed total $k$ -domination number} of $G$ can be similarly defined by changing the closed neighborhood $N_G[v]$ to the open neighborhood $N_G(v)$ in the definition. The \emph{upper signed $k$ -domination number} is the maximum value of $\sum_{v\in V}f(v)$ taken over all \emph{minimal} signed $k$ -dominating functions of $G$ . In this paper, we study these graph parameters from both algorithmic complexity and graph-theoretic perspectives. We prove that for every fixed $k\geq 1$ , the problems of computing these three parameters are all \NP-hard. We also present sharp lower bounds on the signed $k$ -domination number and signed total $k$ -domination number for general graphs in terms of their minimum and maximum degrees, generalizing several known results about signed domination.

preprint2012arXiv

Signed and Minus Domination in Complete Multipartite Graphs

In this paper we determine the exact values of the signed domination number, signed total domination number, and minus domination number of complete multipartite graphs, which substantially generalizes some previous results obtained for special subclasses of complete multipartite graphs such as cliques and complete bipartite graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Hongyu Liang

Research overview

Is this your work?

7 publications

Optimal Rendezvous Strategies for Different Environments in Cognitive Radio Networks

Matroid and Knapsack Center Problems

On the Complexity of $t$ -Closeness Anonymization and Related Problems

On the Complexity of Connectivity in Cognitive Radio Networks Through Spectrum Assignment

On Rainbow- $k$ -Connectivity of Random Graphs

On the Signed (Total) $k$ -Domination Number of a Graph

Signed and Minus Domination in Complete Multipartite Graphs

See the researcher in context

Building this map preview

Hongyu Liang

Research overview

Is this your work?

7 publications

Optimal Rendezvous Strategies for Different Environments in Cognitive Radio Networks

Matroid and Knapsack Center Problems

On the Complexity of ttt-Closeness Anonymization and Related Problems

On the Complexity of Connectivity in Cognitive Radio Networks Through Spectrum Assignment

On Rainbow-kkk-Connectivity of Random Graphs

On the Signed (Total) kkk-Domination Number of a Graph

Signed and Minus Domination in Complete Multipartite Graphs

See the researcher in context

Building this map preview

On the Complexity of $t$ -Closeness Anonymization and Related Problems

On Rainbow- $k$ -Connectivity of Random Graphs

On the Signed (Total) $k$ -Domination Number of a Graph