Implementation of 1/2-Approximation ath Cover Algorithm and Its Empirical Analysis

Junyuan Lin; Guangpeng Ren

Implementation of 1/2-Approximation ath Cover Algorithm and Its Empirical Analysis

Mathematics, Statistics and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In this study, we refine a deterministic algorithm for approximating optimal path covers in graphs, based on Moran et al.'s approach, into two versions: with and without redundant edge removal. Testing on various graph types, including Erdős-Rényi, showed the first version saves 80 while the second cuts computation time by 60 proving their applicability for real-world dense and complex graphs.

Original language	English
Title of host publication	N/A
Place of Publication	PRINCE WAIKIKI RESORT, HONOLULU, HAWAII
State	Published - Jun 1 2024

Keywords

Pure

Access to Document

https://huichawaii.org/wp-content/uploads/2024/07/Lin-Junyuan-2024-HUIC-STEM.pdf

Cite this

@inproceedings{578519e18c6648f2a4b550ea68db0b74,

title = "Implementation of 1/2-Approximation ath Cover Algorithm and Its Empirical Analysis",

abstract = "In this study, we refine a deterministic algorithm for approximating optimal path covers in graphs, based on Moran et al.'s approach, into two versions: with and without redundant edge removal. Testing on various graph types, including Erd{\H o}s-R{\'e}nyi, showed the first version saves 80 while the second cuts computation time by 60 proving their applicability for real-world dense and complex graphs.",

keywords = "Pure",

author = "Junyuan Lin and Guangpeng Ren",

year = "2024",

month = jun,

day = "1",

language = "English",

booktitle = "N/A",

}

TY - GEN

T1 - Implementation of 1/2-Approximation ath Cover Algorithm and Its Empirical Analysis

AU - Lin, Junyuan

AU - Ren, Guangpeng

PY - 2024/6/1

Y1 - 2024/6/1

N2 - In this study, we refine a deterministic algorithm for approximating optimal path covers in graphs, based on Moran et al.'s approach, into two versions: with and without redundant edge removal. Testing on various graph types, including Erdős-Rényi, showed the first version saves 80 while the second cuts computation time by 60 proving their applicability for real-world dense and complex graphs.

AB - In this study, we refine a deterministic algorithm for approximating optimal path covers in graphs, based on Moran et al.'s approach, into two versions: with and without redundant edge removal. Testing on various graph types, including Erdős-Rényi, showed the first version saves 80 while the second cuts computation time by 60 proving their applicability for real-world dense and complex graphs.

KW - Pure

M3 - Conference contribution

BT - N/A

CY - PRINCE WAIKIKI RESORT, HONOLULU, HAWAII

ER -