{"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":"2021-12-06T18:56:35","modified_gmt":"2021-12-06T23:56:35","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":"

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

Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree<\/h2>\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

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":49,"featured_media":0,"parent":12337,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-05-04: Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-05-04 April 20, 2005 Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree Peter J. Taillon\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"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\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"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\/\",\"url\":\"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\/\",\"name\":\"TR-05-04: Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-06T23:55:49+00:00\",\"dateModified\":\"2021-12-06T23:56:35+00:00\",\"description\":\"Carleton University Technical Report TR-05-04 April 20, 2005 Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree Peter J. Taillon\",\"breadcrumb\":{\"@id\":\"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\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"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\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"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\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 2005\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2005\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-05-04: Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-05-04: Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree - School of Computer Science","description":"Carleton University Technical Report TR-05-04 April 20, 2005 Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree Peter J. Taillon","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"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\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"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\/","url":"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\/","name":"TR-05-04: Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-06T23:55:49+00:00","dateModified":"2021-12-06T23:56:35+00:00","description":"Carleton University Technical Report TR-05-04 April 20, 2005 Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree Peter J. Taillon","breadcrumb":{"@id":"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\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["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\/"]}]},{"@type":"BreadcrumbList","@id":"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\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 2005","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2005\/"},{"@type":"ListItem","position":5,"name":"TR-05-04: Improving k-Vertex Cover Algorithms for Graphs of Small Bounded Degree"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13134"}],"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\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13134"}],"version-history":[{"count":3,"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"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}