Dgdrxrt

Why not send Voyager 3 and 4 following up the paths taken by Voyager 1 and 2 to re-transmit signals of later as they fly away from Earth?

How to ask rejected full-time candidates to apply to teach individual courses?

Weaponising the Grasp-at-a-Distance spell

What would you call this weird metallic apparatus that allows you to lift people?

Why are vacuum tubes still used in amateur radios?

How can I prevent/balance waiting and turtling as a response to cooldown mechanics

What initially awakened the Balrog?

White walkers, cemeteries and wights

What is the chair depicted in Cesare Maccari's 1889 painting "Cicerone denuncia Catilina"?

What does 丫 mean? 丫是什么意思？

If Windows 7 doesn't support WSL, then what is "Subsystem for UNIX-based Applications"?

Trying to understand entropy as a novice in thermodynamics

Why weren't discrete x86 CPUs ever used in game hardware?

Test print coming out spongy

Delete free apps from library

The test team as an enemy of development? And how can this be avoided?

Does silver oxide react with hydrogen sulfide?

How can I save and copy a screenhot at the same time?

Would color changing eyes affect vision?

Why is the change of basis formula counter-intuitive? [See details]

A `coordinate` command ignored

GDP with Intermediate Production

What is the difference between a "ranged attack" and a "ranged weapon attack"?

what is the log of the PDF for a Normal Distribution?

Probability for a graph algorithm

7

1

$begingroup$

Let $G = (V, E)$ a graph. A 'dominant set' $W ⊆ V$is a set of nodes, so that for each node $v in V$ holds that either $v$ itself or a neighbor of $v$ is contained in $W$.
Assume that $G$ has minimum degree at least $d > 1$, i.e. each node $v in V$ has degree $deg(v) ≥ d$.

The algorithm consists of two rounds. In the first round we mark each node independently from the other nodes with probability $p$. In the second round we look at each node $v in V$ , if neither $v$ nor any of its neighbours were marked in the first lap, we mark $v$ .

Let $X$ be the number of knots marked in the first round.
So $E(X) = |V|*p$, because $X sim Bin(|V|,p)$, right ?

Let $v ∈ V $any (but fixed) node. If think the probability that neither v nor one of the neighbors of v was marked in the first round would be $(1-p)^deg(v)$ right ? But how can i finde a upper bound which is only dependent from $d$ and $p$ (and not from $v$).

Let $Y$ be the number of knots marked in the second round. How can i finde a upper bound for $E(Y)$.

probability probability-theory graph-theory algorithms

share|cite|improve this question

asked Apr 2 at 9:43

gaeiibogaeiibo

1035

$endgroup$

add a comment | 

7

1

$begingroup$

Let $G = (V, E)$ a graph. A 'dominant set' $W ⊆ V$is a set of nodes, so that for each node $v in V$ holds that either $v$ itself or a neighbor of $v$ is contained in $W$.
Assume that $G$ has minimum degree at least $d > 1$, i.e. each node $v in V$ has degree $deg(v) ≥ d$.

The algorithm consists of two rounds. In the first round we mark each node independently from the other nodes with probability $p$. In the second round we look at each node $v in V$ , if neither $v$ nor any of its neighbours were marked in the first lap, we mark $v$ .

Let $X$ be the number of knots marked in the first round.
So $E(X) = |V|*p$, because $X sim Bin(|V|,p)$, right ?

Let $v ∈ V $any (but fixed) node. If think the probability that neither v nor one of the neighbors of v was marked in the first round would be $(1-p)^deg(v)$ right ? But how can i finde a upper bound which is only dependent from $d$ and $p$ (and not from $v$).

Let $Y$ be the number of knots marked in the second round. How can i finde a upper bound for $E(Y)$.

probability probability-theory graph-theory algorithms

share|cite|improve this question

asked Apr 2 at 9:43

gaeiibogaeiibo

1035

$endgroup$

add a comment | 

$begingroup$

Let $G = (V, E)$ a graph. A 'dominant set' $W ⊆ V$is a set of nodes, so that for each node $v in V$ holds that either $v$ itself or a neighbor of $v$ is contained in $W$.
Assume that $G$ has minimum degree at least $d > 1$, i.e. each node $v in V$ has degree $deg(v) ≥ d$.

The algorithm consists of two rounds. In the first round we mark each node independently from the other nodes with probability $p$. In the second round we look at each node $v in V$ , if neither $v$ nor any of its neighbours were marked in the first lap, we mark $v$ .

Let $X$ be the number of knots marked in the first round.
So $E(X) = |V|*p$, because $X sim Bin(|V|,p)$, right ?

Let $v ∈ V $any (but fixed) node. If think the probability that neither v nor one of the neighbors of v was marked in the first round would be $(1-p)^deg(v)$ right ? But how can i finde a upper bound which is only dependent from $d$ and $p$ (and not from $v$).

Let $Y$ be the number of knots marked in the second round. How can i finde a upper bound for $E(Y)$.

probability probability-theory graph-theory algorithms

share|cite|improve this question

asked Apr 2 at 9:43

gaeiibogaeiibo

1035

$endgroup$

share|cite|improve this question

asked Apr 2 at 9:43

gaeiibogaeiibo

1035

share|cite|improve this question

asked Apr 2 at 9:43

gaeiibogaeiibo

1035

asked Apr 2 at 9:43

gaeiibogaeiibo

1035

asked Apr 2 at 9:43

gaeiibogaeiibo

1035

1 Answer
1

active

oldest

votes

1

$begingroup$

The probability of being selected in the second round is $(1-p)^textdeg(v)colorred+1$.

Use the fact that $deg v ge d$ to conclude that $(1-p)^deg v+1le (1-p)^d+1$. Then $EYle |V|(1-p)^d+1$.

share|cite|improve this answer

answered Apr 2 at 21:50

Mike EarnestMike Earnest

28.2k22152

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3171665%2fprobability-for-a-graph-algorithm%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

The probability of being selected in the second round is $(1-p)^textdeg(v)colorred+1$.

Use the fact that $deg v ge d$ to conclude that $(1-p)^deg v+1le (1-p)^d+1$. Then $EYle |V|(1-p)^d+1$.

share|cite|improve this answer

answered Apr 2 at 21:50

Mike EarnestMike Earnest

28.2k22152

$endgroup$

add a comment | 

1

$begingroup$

The probability of being selected in the second round is $(1-p)^textdeg(v)colorred+1$.

Use the fact that $deg v ge d$ to conclude that $(1-p)^deg v+1le (1-p)^d+1$. Then $EYle |V|(1-p)^d+1$.

share|cite|improve this answer

answered Apr 2 at 21:50

Mike EarnestMike Earnest

28.2k22152

$endgroup$

add a comment | 

$begingroup$

The probability of being selected in the second round is $(1-p)^textdeg(v)colorred+1$.

Use the fact that $deg v ge d$ to conclude that $(1-p)^deg v+1le (1-p)^d+1$. Then $EYle |V|(1-p)^d+1$.

share|cite|improve this answer

answered Apr 2 at 21:50

Mike EarnestMike Earnest

28.2k22152

$endgroup$

share|cite|improve this answer

answered Apr 2 at 21:50

Mike EarnestMike Earnest

28.2k22152

answered Apr 2 at 21:50

Mike EarnestMike Earnest

28.2k22152

answered Apr 2 at 21:50

Mike EarnestMike Earnest

28.2k22152