# Indivisual Study II(AM)

[TOC]

## Week 1
* frog3 and grid2
* discuss topics
* flow and LP
* 2017_IEEEMC_Barrier_Coverage.pdf
* waked up enable radio m-IOT
* paper

## Week 2
no meeting for personal law issue

## Week 3

### Distributed construction of minimum Connected Dominating Set in wireless sensor network using two-hop information

#### link
https://www.sciencedirect.com/science/article/pii/S1389128617302177

#### introduction
* try to solve Minimal Connected Dominating Set Problem(MCDS)
* a greedy algorithm proposed by the team
* former algorithms
* (4.8 + ln 5)|opt| + 1.2

#### terms
* steiner tree
* independent set, IS
* maxmimal => MIS
* dominant set, DS
* connected => CDS
* pseudo => PDS
* unit disk graph, UDG

#### the algorithm

##### step 1 : construct PDS
* use 1-hop and 2-hop neighbours’ information
* do while
* select nodes(can be multiple)
* degree(u) > deg(neighor of u) and deg(neibor of neibor of u)
* all adjacent nodesbecome dominatees
* delete dominatees +incident edges
* update degree
* until all white nodes form an IS

* better than MIS method
* note MIS is a dominating set itself

##### step 2 : Improved Steiner Tree construction
* connection-load(for a candicate vertex)
* current count of number of components it is connected with
* do while
* select node(one)
* until done

##### step 3 : Removal of Redundant Dominators

* for gray
* connected to the CDS through only one connector
* connected to the CDS through two connectors and they are adjacent

* for black and connecting points
* all the dominatees of a dominator x are adjacent to some other dominators or connectors
* x is connected to the CDS by one connector or is connected to the CDS by two connectors and they are adjacent

#### algorithm detail (distributed scheme)

##### Data
- color
- node ID
- original degree
- effective degree
- white vertices adjacent to it
- 1-HopNebsTable
- 2-HopNebsTable
- above info +
- [multi-valued attribute](https://www.google.com/search?q=multi-valued+attribute&oq=multi-valued+attribute&aqs=chrome..69i57j0l7.333j0j7&sourceid=chrome&ie=UTF-8) mutual neighbor, mnColor
- cdsList
- CDS members of the component of u
- connectionCount
- c.c. count adjacent to u
- rivalList
- the dominatees of c.c. of u which are adjacent to u

#### algorithm analysis

### Tree5 LP to flow ...

### A Robust Time Synchronization Scheme for Industrial Internet of Things

### An Approximation Algorithm for the Maximum-Lifetime Data Aggregation Tree Problem in Wireless Sensor Networks

### Towards minimum-delay and energy-efficient flooding in low-duty-cycle wireless sensor networks

### Concpets
* flooding tree
* aggregation tree
* connected dominating set
* k-connected m-dominating set

## Week 4 cont.

## Week 5 holiday

## Week 6 cont. paper
[Distributed construction of minimum Connected Dominating Set in wireless sensor network using two-hop information](/uFYJNIFkQ4Sq20i6RXeAyA)

## Week 6
- nxt algo 2 finish reading before meeting
- some result of previous student
- constraint on graph or more info. than distributed
cut vertex
cactus
ear decomposition / decomposition

[references](https://www2.seas.gwu.edu/~cheng/Publication/CDSSurvey-Handbook.pdf)

## Week 7

### before meeting

### nouns
- ad hoc network
- unit disk graph
- sensor r identical
- homogeneous, hetrogeneous
- N[v] - not include v
- N(v) - include v
- N[S], N(S)

### survey tool
- web of science, NCTU

### change of problem
- generalize / restriction original problem

### labeling
- dis small => label dis large

### intersection graph
- UDG

### paper - UDG, DM. , studies UDG graph equivalence

### paper - vector domination in split-indifference graph
- vector domination(R-dominating set)
- each point assign [0, deg(v)]
- either choose it or not choose it with # chosen neigbor >= R(v)
- split-indifference graph

### n-backbone CDS, harder

### split graph
- S+K
- S isolated
- K complete
- S, K can connect arbitrary

### Case STUDY - Minimal Vector CDS

## pre Week 8 - survey @ 4/18/2020
- Two Meta-Heuristics Designed to Solve the Minimum Connected Dominating Set Problem for Wireless Networks Design and Management
- MA
- An intelligent backbone formation algorithm for wireless ad hoc networks based on distributed learning automata, 2020
- Self-stabilizing Algorithm for Generic Aggregated Weighted Connected Dominating Set
- Two-Hop Neighborhood Information Joint Double Broadcast Radius for Effective Code Dissemination in WSNs, 2019
- citation 12
- Q1 journal
- A balanced energy efficient virtual backbone construction algorithm in wireless sensor networks
- Q2, 2019
- A Polynomial-Time Approximation Scheme for theMinimum-Connected Dominating Set in Ad Hoc WirelessNetworks
- for concepts and lemmas

## Week 8

### Problem
- cactus
- e in at most in cycle
- eq: each block is a cycle or path
- block: maximal connected subgraph that has no cut vertex
- usage
- k-cactus
- len of max cycle <= k
- mine: limit on # of cycle
- hop domination
- mine + survey
- mine : can change to dis <= not =
- cactus graph CDS
- info.
- distibution
- mine
- power dominating set
- fill chain
- n, k, maximize the dominated points(k connect or not connect)
- mine
- weighted k-domination
- if not in S, at least k neighor
- weight minimize
- mine : vetex weight sum > k

### Candicate
- cactus graph CDS
- trivial
- neighbor vetex weight sum >= k
- n, k, maximize the dominated points
- k-hop domination modified to dis<=k
- hard problem on k-cactus
- ex: 4
- increnental, progressive, step by step
- r-domination

### Trick
- diameter decomposition)
- proof by P

### Survey
- Algorithm and hardness results on hop domination in graphs
- hop domination
- Trees with Unique Minimum Semitotal Dominating Sets
- cactus graph connected dominating set
- Mutual transferability for (F, B, R)-domination on strongly chordal graphs and cactus graphs
- D1 to D2
- chen and her student
- A LINEAR ALGORITHM FOR FINDING A MINIMUM DOMINATING SET IN A CACTUS
- On Domination, 2-Domination, and Italian Domination Numbers
- Power domination in graphs

## Week 9
- rest

## Week 10
- Ttee greedy
- tree dp
- cactus gen
- Kuratowski's Theorem
- is planar iff not contatin any subdivisions of K33 or K5
- Collogary:
- Cacti are planar graphs
- Key: how to find in O(n^2)
- O(n^2)
- to try:
- induction on block
- end block proofing technique
- 張鎮華-台大數學教授-dominating set

## Week 11

- [Individual Study Report AM 2020 spring](/2YQH3yw0RHGDGdsvvJsxJw)
- domination for cactus
- https://www.sciencedirect.com/science/article/pii/0166218X86900892

## Week 12
- busy doing AI lab3 and analysis midterm 2