NIST · ИТ · 961b794e89dd3413f6a7
Linear Time Vertex Partitioning on Massive Graphs
The problem of optimally removing a set of vertices from a graph to minimize the size of the largest resultant component is known to be NP-complete. Prior work has provided near optimal heuristics with a high time complexity that function on up to hundreds
NIST · ИТОфициальный источник · 2016-03-07
{
"title_en": "Linear Time Vertex Partitioning on Massive Graphs",
"designation": "",
"series": "",
"status": "",
"date": "2016-03-07",
"date_original": "March 7, 2016",
"url": "https://www.nist.gov/publications/linear-time-vertex-partitioning-massive-graphs",
"source": "NIST Publications",
"display_en": "",
"authors_en": "Peter M. Mell , Richard Harang, Assane Gueye",
"abstract_excerpt_en": "The problem of optimally removing a set of vertices from a graph to minimize the size of the largest resultant component is known to be NP-complete. Prior work has provided near optimal heuristics with a high time complexity that function on up to hundreds",
"id": "961b794e89dd3413f6a7",
"sources": [
"NIST Publications"
],
"source_records": [
{
"title_en": "Linear Time Vertex Partitioning on Massive Graphs",
"designation": "",
"series": "",
"status": "",
"date": "2016-03-07",
"date_original": "March 7, 2016",
"url": "https://www.nist.gov/publications/linear-time-vertex-partitioning-massive-graphs",
"source": "NIST Publications",
"display_en": "",
"authors_en": "Peter M. Mell , Richard Harang, Assane Gueye",
"abstract_excerpt_en": "The problem of optimally removing a set of vertices from a graph to minimize the size of the largest resultant component is known to be NP-complete. Prior work has provided near optimal heuristics with a high time complexity that function on up to hundreds"
}
],
"translation_state": "none",
"possible_title_matches": 1
}