BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Hongyu Liang

Hongyu Liang appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete MathematicsData Structures and Algorithmsmath.CODatabasesNetworking and Internet Architecture

Catalog footprint

What is connected

7works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

7 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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+ε$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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)$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access