2011-01-01, English, Article, Journal or magazine article edition: A generalization of Nemhauser and Trotter's local optimization theorem Fellows, Michael; Guo, Jiong; Moser, Hannes; ...

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/208446679
Physical Description
  • Journal Article
Published
  • Academic Press, 2011-01-01
Language
  • English

Edition details

Title
  • A generalization of Nemhauser and Trotter's local optimization theorem
Author
  • Fellows, Michael
  • Guo, Jiong
  • Moser, Hannes
  • Niedermeier, Rolf
Published
  • Academic Press, 2011-01-01
Physical Description
  • Journal Article
Subjects
Summary
  • The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotters result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away &​quot;easy parts&​quot; of the input instance, finally leaving a &​quot;hard core&​quot; whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of Vertex Cover, called Bounded-Degree Vertex Deletion. For some fixed d&​ge;0, Bounded-Degree Vertex Deletion asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d=​0. Our generalization of the Nemhauser-Trotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an O(k)-vertex problem kernel for d&​le;1 and, for any &​omega;&​gt;0, an O(k1+&​omega;)-vertex problem kernel for d&​ge;2. Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.
Language
  • English
Identifier
  • oai:espace.cdu.edu.au:cdu:37873

Get this edition

  • Set up My libraries

    How do I set up "My libraries"?

    In order to set up a list of libraries that you have access to, you must first login or sign up. Then set up a personal list of libraries from your profile page by clicking on your user name at the top right of any screen.

  • All (1)
  • NT (1)
None of your libraries hold this item.

This single location in All:

Library Access Call number(s) Formats held Language
Charles Darwin University. Charles Darwin University Institutional Repository. Open to the public Article; Journal or magazine article English
Show 0 more libraries...
None of your libraries hold this item.
None of your libraries hold this item.

This single location in Northern Territory:

Library Access Call number(s) Formats held Language
Charles Darwin University. Charles Darwin University Institutional Repository. Open to the public Article; Journal or magazine article English
Show 0 more libraries...
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment