{"id":13134,"date":"2021-12-06T18:55:49","date_gmt":"2021-12-06T23:55:49","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13134"},"modified":"2026-06-02T14:59:24","modified_gmt":"2026-06-02T18:59:24","slug":"tr-05-04-improving-k-vertex-cover-algorithms-for-graphs-of-small-bounded-degree","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2005\/tr-05-04-improving-k-vertex-cover-algorithms-for-graphs-of-small-bounded-degree\/","title":{"rendered":"TR-05-04: Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-05-04: Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-05-04
\nApril 20, 2005<\/p>\n\n\n\n

Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
Peter J. Taillon<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n

In this report we describe a new approach to improve algorithms for solving the k-Vertex Cover problem. The algorithm uses graph cutting, during the tree search phase, as a basis for identifying, disconnecting, and processing small fractions of the residual graph. Unlike previous methods that use separator theorems constrained to restricted graph classes and requiring complex dynamic programming, this algorithm applies to graphs of small, bounded degree, uses existing branching rules and incurs no any additional complexity.Such graph instances are generated during the tree search phases of the current best FPT k-vertex cover algorithms. Any future advances in sequential algorithms for the k-Vertex Cover problem can incorporate this approach, thus improving their complexity.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

TR-05-04.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-05-04 April 20, 2005 Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree Peter J. Taillon Abstract In this report we describe a new approach to improve algorithms for solving the k-Vertex Cover problem. The algorithm uses graph cutting, during the tree search phase, as a basis for identifying, disconnecting, […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12337,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13134","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13134","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13134"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13134\/revisions"}],"predecessor-version":[{"id":13138,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13134\/revisions\/13138"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12337"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13134"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13134"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}