Scribd
Upload
52 views26 pages

Final Project 2021

The document provides instructions for a final project on finding the maximum k-core of a graph. Students are asked to write a program that takes a graph as input and outputs the maximum k-core subgraph. The maximum k-core is the largest subgraph where all vertices have a degree of at least k. Examples are given of finding the 3-core of sample graphs by iteratively removing vertices of the lowest degree. Guidelines are provided on pseudo-code, testing, grading criteria, and project deadlines.

Uploaded by

梁瑋麟
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
52 views26 pages

Final Project 2021

The document provides instructions for a final project on finding the maximum k-core of a graph. Students are asked to write a program that takes a graph as input and outputs the maximum k-core subgraph. The maximum k-core is the largest subgraph where all vertices have a degree of at least k. Examples are given of finding the 3-core of sample graphs by iteratively removing vertices of the lowest degree. Guidelines are provided on pseudo-code, testing, grading criteria, and project deadlines.

Uploaded by

梁瑋麟
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 26

Discrete Mathematics #Final

2021/12/13
Final Project - Maximum k-core

• A k-core of a graph G is a maximal subgraph of G in which all


vertices have degree at least k.

• Find the maximum k-core in the simple graph G.

• Existing source codes are forbidden.


◦ Packages for graph or network are also forbidden (Ex. NetworkX)

• No plagiarism.
Format

• Input (Graph): • Output (Maximum k-core):


01 3-core
02 12
12 14
14 15
15 24
23 25
24 45
25
45
Example-1

• Input (Graph):
01
02 0
12 1
2
14
15
23 5
24 4 3
25
45
Example-1

• Create 2-core graph: Remove the vertex with degree 1.

1
2

5
4 3
Example-1

• All vertices in 2-core graph have degree at least 2.

1
2

5
4
Example-1

• Create 3-core graph: Remove the vertex with degree 2.

1
2

5
4
Example-1

• All vertices in 3-core graph have degree at least 3.


• The maximum k-core is 3-core.

1
2

5
4
Example-2

• Find the maximum k-core for the following graph.


Example-2

• Create 2-core graph: Remove the vertex with degree 1.


Example-2

• Create 2-core graph: Remove the vertex with degree 1.


Example-2

• All vertices in 2-core graph have degree at least 2.


Example-2

• Create 3-core graph: Remove the vertex with degree 2.


Example-2

• All vertices in 3-core graph have degree at least 3.


• The maximum k-core is 3-core
Example-3

• Find the maximum k-core for the following graph.


Example-3

• Create 2-core graph: Remove the vertex with degree 1.


Example-3

• Create 3-core graph: Remove the vertex with degree 2.


Example-3

• Create 3-core graph: Remove the vertex with degree 2.


Example-3

• All vertices in 3-core graph have degree at least 3.


• The maximum k-core is 3-core
Pseudo Code

• How to optimize the search of existing vertices?


• DFS/BFS from the lowest node degree?
• Any other method?
Test Data

• Number of test cases: 10


• Time limit: 4000ms
• Memory limit: 1000000KiB
• 4% for each test case, all 10 test cases = 40%
Grading Policy

1. Correctness (40%)
2. Speed (20%)
• Top 25%: 20%
• Top 50%: 15%
• Top 75%: 10%
• The rest: 5%
3. Report (40%)
• English / Chinese
• Novelty – Using what kind of method to save more time?
• Comprehensiveness of experiments – Any comparisons with different
searching methods?
• Theoretical results – Is there any way to describe or prove the
complexity of your algorithm?
Important Dates

• 1/13 (Thu) 23:59 - Formosa OJ closed


• 1/16 (Sun) 23:59 - Report & Code Submission deadline
If you have any question…

• We encourage everyone to ask any question in TA hours.


• 10:00-12:00 every Friday online
• https://meet.google.com/yuf-bghs-vqk

• If the question is personal or the time slot is not available


to you, please send an email to TAs.
• Ex: TAs miss to approve your Formosa OJ request.
Q&A
Thank you

You might also like