Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover

DOI10.1007/3-540-44634-6_8MaRDI QIDQ4778544zbMATH OpenFDO

Authors N. Nishimura, Dimitrios M. Thilikos, Prabhakar Ragde

Publication date 18 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2125/21250075

zbMATH Keywords

fast algorithmsminor-minimal graphsobstructionsrecognition algorithm

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• An improved fixed-parameter algorithm for vertex cover
• A characterization of graphs with vertex cover up to five
• On efficient fixed-parameter algorithms for weighted vertex cover
• Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs

Cited in

(9)

• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• A characterization of graphs with vertex cover six
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications
• A characterization of graphs with vertex cover up to five
• Minor‐order obstructions for the graphs of vertex cover 6
• Parameterized Reductions and Algorithms for Another Vertex Cover Generalization
• k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms
• Faster parameterized algorithms for modification problems to minor-closed classes

This page was built for publication: Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4778544)