The degeneracy of an n-vertex graph G is the smallest number d such that every subgraph of G contains a vertex of degree at most d. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for en...
详细信息
ISBN:
(纸本)9783642175169
The degeneracy of an n-vertex graph G is the smallest number d such that every subgraph of G contains a vertex of degree at most d. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic bron-kerbosch algorithm and show that it runs in time O(dn3(d/3)). We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an n-vertex graph with degeneracy d (when d is a multiple of 3 and n >= d + 3) is (n - d)3(d/3). Therefore, our algorithm matches the Theta(d(n - d)3(d/3)) worst-case output size of the problem whenever n - d = Omega(n).
We implement a new algorithm for listing all maximal cliques in sparse graphs due to Eppstein, Loffler, and Strash (ISAAC 2010) and analyze its performance on a large corpus of real-world graphs. Our analysis shows th...
详细信息
ISBN:
(纸本)9783642206610
We implement a new algorithm for listing all maximal cliques in sparse graphs due to Eppstein, Loffler, and Strash (ISAAC 2010) and analyze its performance on a large corpus of real-world graphs. Our analysis shows that this algorithm is the first to offer a practical solution to listing all maximal cliques in large sparse graphs. All other theoretically-fast algorithms for sparse graphs have been shown to be significantly slower than the algorithm of Tomita et al. (Theoretical Computer Science, 2006) in practice. However, the algorithm of Tomita et al. uses an adjacency matrix, which requires too much space for large sparse graphs. Our new algorithm opens the door for fast analysis of large sparse graphs whose adjacency matrix will not fit into working memory.
The current specification of the IEEE 802.15.4 standard supports several application specific Quality of Service (QoS) requirements for Internet of Things (IoT) network applications. Specifically, the Time Slotted Cha...
详细信息
ISBN:
(纸本)9781665435741
The current specification of the IEEE 802.15.4 standard supports several application specific Quality of Service (QoS) requirements for Internet of Things (IoT) network applications. Specifically, the Time Slotted Channel Hopping (TSCH) MAC mode provides effective latency and throughput performance through the use of dedicated timeslots between two communicating devices. Despite the impact TSCH MAC can facilitate in low-power lossy networks (LLNs), the standard does not explore either the building or maintaining of a schedule. The challenge is to build an energy-efficient TSCH schedule that repeats periodically over several channels. To address this problem, we propose a centralized cluster-level TSCH scheduling mechanism from the energy-efficiency perspective. The proposed mechanism derives a collision graph for each of the clusters in the network topology to schedule non-overlapping timeslots. The bron-kerbosch algorithm is used as a sub-procedure for finding the complete sub-graphs of a graph. In addition, we analytically compute the transmission and energy overhead with the help of a Markov Model for TSCH.
暂无评论