Maximum Independent Set in Trees (Linear Time Algorithm) - Easy Theory
Here we give a linear time algorithm for the maximum independent set problem for trees. A tree is a graph without cycles, and an independent set is a set of vertices without edges between them. The trick here is that trees don't have cycles, so answering a question about a vertex and its neighbors partitions the rest of the vertices into "clusters" that have no vertices in common. So we can solve the problem independently for each of the neighbors.
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory #gate #theory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy, Ben Pritchard
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
Видео Maximum Independent Set in Trees (Linear Time Algorithm) - Easy Theory канала Easy Theory
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory #gate #theory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy, Ben Pritchard
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
Видео Maximum Independent Set in Trees (Linear Time Algorithm) - Easy Theory канала Easy Theory
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
![What is a graph? Endless Definitions! - Easy Theory](https://i.ytimg.com/vi/iwcqjM-shQI/default.jpg)
![Max Contiguous Subarray Sum - Cubic Time To Kadane's Algorithm ("Maximum Subarray" on LeetCode)](https://i.ytimg.com/vi/2MmGzdiKR9Y/default.jpg)
![Here’s why Mr Beast is a GENIUS - How He Grew his YouTube Channel](https://i.ytimg.com/vi/JJ-ogw8AZ3o/default.jpg)
![Time does not exist: Carlo Rovelli at TEDxLakeComo](https://i.ytimg.com/vi/xeHHjGKwZWM/default.jpg)
![Complete Proof of an Inherently Ambiguous Context-Free Language - Easy Theory](https://i.ytimg.com/vi/FmX4FEeX_G0/default.jpg)
![Chemical Curiosities: Surprising Science and Dramatic Demonstrations - with Chris Bishop](https://i.ytimg.com/vi/ti_E2ZKZpC4/default.jpg)
![Public Key Cryptography: RSA Encryption Algorithm](https://i.ytimg.com/vi/wXB-V_Keiu8/default.jpg)
![1. Algorithmic Thinking, Peak Finding](https://i.ytimg.com/vi/HtSuA80QTyo/default.jpg)
![The "Master" Theorem/Method, Derivation - Easy Theory](https://i.ytimg.com/vi/ZGmUTe1uiE0/default.jpg)
![The Science of Fireworks - with Chris Bishop](https://i.ytimg.com/vi/rmtK2BgmGCw/default.jpg)
![GATE 2020 Question 42 (p Factorial Trick, Hard Pumping Lemma!) - Easy Theory](https://i.ytimg.com/vi/qVnXMXt6Ww0/default.jpg)
![Independent Vertex Sets | Graph Theory, Maximal and Maximum Independent Sets](https://i.ytimg.com/vi/0stavxEccvE/default.jpg)
![Regular Languages Closed Under Inverse (Homo)Morphism - Easy Theory](https://i.ytimg.com/vi/utlPZgorDLg/default.jpg)
![Kadane's Algorithm - Maximum Sum Subarray (Amazon Coding Interview Question)](https://i.ytimg.com/vi/jnoVtCKECmQ/default.jpg)
![Counting Sort: An Exploration of Sorting Special Input In Linear Time](https://i.ytimg.com/vi/1mh2vilbZMg/default.jpg)
![What even IS a PDA (Pushdown Automaton)? Motivation + Description - Easy Theory](https://i.ytimg.com/vi/Br44Zxv84-Q/default.jpg)
![PDA to CFG Conversion (Pushdown Automaton to Context-Free Grammar) - Easy Theory](https://i.ytimg.com/vi/X0nrYIVGs3M/default.jpg)
![A PDA example for {0^n 1^n : n at least 0} - Easy Theory](https://i.ytimg.com/vi/SSJ0i-I2VXU/default.jpg)
![Everything and Nothing: What is Nothing? (Jim Al-Khalili) | Science Documentary | Science](https://i.ytimg.com/vi/rKPv8zApee0/default.jpg)
![Simple Simplifications to PDAs (Force the Stack to be Empty!) - Easy Theory](https://i.ytimg.com/vi/dBdLhz14NSE/default.jpg)