Search results for "minimum vertex cover"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Martin Pelikan, Rajiv Kalapala, Alexander K. Hartmann	Hybrid evolutionary algorithms on minimum vertex cover for random graphs.	GECCO	2007	DBLP DOI BibTeX RDF	minimum vertex cover, genetic algorithm, simulated annealing, branch and bound, hierarchical BOA
2	Yuichi Yoshida, Masaki Yamamoto, Hiro Ito	An improved constant-time approximation algorithm for maximum~matchings.	STOC	2009	DBLP DOI BibTeX RDF	constant-time approximation algorithms, minimum vertex cover, property testing, maximum matching, minimum set cover
2	Barbara Mazbic-Kulma, Krzysztof Sep	Some Approximation Algorithms for Minimum Vertex Cover in a Hypergraph.	Computer Recognition Systems 2	2008	DBLP DOI BibTeX RDF
2	Xiaoming Chen, Zheng Tang, Xinshun Xu, Songsong Li, Guangpu Xia, Jiahai Wang	An Algorithm Based on Hopfield Network Learning for Minimum Vertex Cover Problem.	ISNN	2004	DBLP DOI BibTeX RDF
2	Edith Hemaspaandra, Jörg Rothe, Holger Spakowski	Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.	WG	2002	DBLP DOI BibTeX RDF	minimum vertex cover heuristics, parallel access to NP, Computational complexity, approximation, completeness
1	Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld	A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.	SODA	2012	DBLP BibTeX RDF
1	Shaohua Li, Jianxin Wang, Jianer Chen, Zhijian Wang	An Algorithm for Minimum Vertex Cover Based on Max-I Share Degree.	JCP	2011	DBLP DOI BibTeX RDF
1	Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld	A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size	CoRR	2011	DBLP BibTeX RDF
1	Shaowei Cai, Kaile Su, Abdul Sattar	Local search with edge weighting and configuration checking heuristics for minimum vertex cover.	Artif. Intell.	2011	DBLP DOI BibTeX RDF
1	Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz	Minimum vertex cover in rectangle graphs.	Comput. Geom.	2011	DBLP DOI BibTeX RDF
1	Oded Goldreich	Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.	Studies in Complexity and Cryptography	2011	DBLP DOI BibTeX RDF
1	Xuncai Zhang, Wenjun Song, Ruili Fan, Guangzhao Cui	Three Dimensional DNA Self-Assembly Model for the Minimum Vertex Cover Problem.	ISCID	2011	DBLP DOI BibTeX RDF
1	Xuncai Zhang, Ying Niu, Yanfeng Wang	DNA Computing in Microreactors: A Solution to the Minimum Vertex Cover Problem.	BIC-TA	2011	DBLP DOI BibTeX RDF
1	Babak Behsaz, Pooya Hatami, Ebadollah S. Mahmoodian	On minimum vertex cover of generalized Petersen graphs	CoRR	2010	DBLP BibTeX RDF
1	Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz	Minimum Vertex Cover in Rectangle Graphs	CoRR	2010	DBLP BibTeX RDF
1	Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz	Minimum Vertex Cover in Rectangle Graphs.	ESA	2010	DBLP DOI BibTeX RDF
1	Yong Zhang, Francis Y. L. Chin, Hing-Fung Ting	Approximated Distributed Minimum Vertex Cover Algorithms for Bounded Degree Graphs.	COCOON	2010	DBLP DOI BibTeX RDF
1	Shaowei Cai, Kaile Su, Qingliang Chen	EWLS: A New Local Search for Minimum Vertex Cover.	AAAI	2010	DBLP BibTeX RDF
1	Kamanashis Biswas, S. A. M. Harun	Constraint Minimum Vertex Cover in K Partite Graph, Approximation Algorithm and Complexity Analysis	CoRR	2009	DBLP BibTeX RDF
1	Ali D. Mehrabi, Saeed Mehrabi, Abbas Mehrabi	A Pruning based Ant Colony Algorithm for Minimum Vertex Cover Problem.	IJCCI	2009	DBLP BibTeX RDF
1	Stefan Kratsch, Frank Neumann	Fixed-parameter evolutionary algorithms and the vertex cover problem.	GECCO	2009	DBLP DOI BibTeX RDF	evolutionary algorithms, combinatorial optimization, multi-objective optimization, runtime analysis
1	Tammy M. K. Cheng, Yu-En Lu, Pietro Liò	Identification of structurally important amino acids in proteins by graph-theoretic measures.	KDD Workshop on Statistical and Relational Learning in Bioinformatics	2009	DBLP DOI BibTeX RDF	protein stability, graph theory, computational biology, vertex cover, protein structure
1	Madhur Tulsiani	CSP gaps and reductions in the lasserre hierarchy.	STOC	2009	DBLP DOI BibTeX RDF	constraint satisfaction, semidefinite programming, integrality gaps
1	Sharon Marko, Dana Ron	Approximating the distance to properties in bounded-degree and general sparse graphs.	ACM Transactions on Algorithms	2009	DBLP DOI BibTeX RDF	Sublinear approximation algorithms, property testing, graph properties, distance approximation
1	Carsten Witt	Greedy Local Search and Vertex Cover in Sparse Random Graphs.	TAMC	2009	DBLP DOI BibTeX RDF
1	Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, Jara Uitto	A Local 2-Approximation Algorithm for the Vertex Cover Problem.	DISC	2009	DBLP DOI BibTeX RDF
1	Parthasarathy Guturu, Ram Dantu	An Impatient Evolutionary Algorithm With Probabilistic Tabu Search for Unified Solution of Some NP-Hard Problems in Graph and Set Theory via Clique Finding.	IEEE Transactions on Systems, Man, and Cybernetics, Part B	2008	DBLP DOI BibTeX RDF
1	Jean Cardinal, Eythan Levy	Connected Vertex Covers in Dense Graphs.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF	connected vertex cover, dense graph, approximation algorithm, vertex cover
1	Andreas Wiese, Evangelos Kranakis	Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs.	DCOSS	2008	DBLP DOI BibTeX RDF
1	Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, Saket Saurabh	Graph Layout Problems Parameterized by Vertex Cover.	ISAAC	2008	DBLP DOI BibTeX RDF
1	Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar	König Deletion Sets and Vertex Covers above the Matching Size.	ISAAC	2008	DBLP DOI BibTeX RDF
1	Mark Hauschild, Martin Pelikan	Enhancing Efficiency of Hierarchical BOA Via Distance-Based Model Restrictions.	PPSN	2008	DBLP DOI BibTeX RDF
1	Jianxin Wang, Xiaoshuang Xu, Jianer Chen	Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs.	J. Comput. Sci. Technol.	2008	DBLP DOI BibTeX RDF	Min-CVCB, parameter complexity, chain implication, approximation algorithm
1	Michal Parnas, Dana Ron	Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms.	Theor. Comput. Sci.	2007	DBLP DOI BibTeX RDF
1	Miroslav Chlebík, Janka Chlebíková	Minimum 2SAT-DELETION: Inapproximability results and relations to Minimum Vertex Cover.	Discrete Applied Mathematics	2007	DBLP DOI BibTeX RDF
1	Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz	Optimization problems in multiple-interval graphs.	SODA	2007	DBLP DOI BibTeX RDF
1	Faisal N. Abu-Khzam, Nagiza F. Samatova, Mohamad A. Rizk, Michael A. Langston	The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover.	AICCSA	2007	DBLP DOI BibTeX RDF
1	Jianxin Wang, Xiaoshuang Xu, Yunlong Liu	An Exact Algorithm Based on Chain Implication for the Min-CVCB Problem.	COCOA	2007	DBLP DOI BibTeX RDF
1	Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar, C. R. Subramanian	The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number.	ISAAC	2007	DBLP DOI BibTeX RDF
1	Jianxin Wang, Xiaoshuang Xu, Jianer Chen	An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs.	TAMC	2007	DBLP DOI BibTeX RDF
1	Alexander Grigoriev, Hans L. Bodlaender	Algorithms for Graphs Embeddable with Few Crossings per Edge.	Algorithmica	2007	DBLP DOI BibTeX RDF
1	Marius Nagy, Selim G. Akl	Real-time minimum vertex cover for two-terminal series-parallel graphs.	IJHPCN	2006	DBLP DOI BibTeX RDF
1	Xinshun Xu, Jun Ma	An efficient simulated annealing algorithm for the minimum vertex cover problem.	Neurocomputing	2006	DBLP DOI BibTeX RDF
1	Erik Jan van Leeuwen	Better Approximation Schemes for Disk Graphs.	SWAT	2006	DBLP DOI BibTeX RDF
1	Emma Rollon, Javier Larrosa	Bucket elimination for multiobjective optimization problems.	J. Heuristics	2006	DBLP DOI BibTeX RDF	Dynamic programming, Multiobjective optimization, Global constraints, Decomposition methods
1	Michal Parnas, Dana Ron	On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms	Electronic Colloquium on Computational Complexity (ECCC)	2005	DBLP BibTeX RDF
1	Jianer Chen, Iyad A. Kanj	On approximating minimum vertex cover for graphs with perfect matching.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
1	Jean Cardinal, Martine Labbé, Stefan Langerman, Eythan Levy, Hadrien Mélot	A Tight Analysis of the Maximal Matching Heuristic.	COCOON	2005	DBLP DOI BibTeX RDF
1	Alexander Grigoriev, Hans L. Bodlaender	Algorithms for Graphs Embeddable with Few Crossings Per Edge.	FCT	2005	DBLP DOI BibTeX RDF
1	Jun Kiniwa	Approximation of Self-stabilizing Vertex Cover Less Than 2.	Self-Stabilizing Systems	2005	DBLP DOI BibTeX RDF
1	Erik Jan van Leeuwen	Approximation Algorithms for Unit Disk Graphs.	WG	2005	DBLP DOI BibTeX RDF
1	Xinshun Xu, Zheng Tang, Rong Long Wang, XuGang Wang	A new motion equation for the minimum vertex cover problem.	Neurocomputing	2004	DBLP DOI BibTeX RDF
1	Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer	What cannot be computed locally!	PODC	2004	DBLP DOI BibTeX RDF	approximation hardness, distributed algorithms, locality, lower bounds, dominating set, vertex cover, maximal independent set, maximal matching
1	Miroslav Chlebík, Janka Chlebíková	On Approximation Hardness of the Minimum 2SAT-DELETION Problem.	MFCS	2004	DBLP DOI BibTeX RDF
1	Miroslav Chlebík, Janka Chlebíková	Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized Complexity.	SWAT	2004	DBLP DOI BibTeX RDF
1	Jianer Chen, Iyad A. Kanj	Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms.	J. Comput. Syst. Sci.	2003	DBLP DOI BibTeX RDF
1	Ana Paula Tomás, António Leslie Bajuelos, Fábio Marques	Approximation Algorithms to Minimum Vertex Cover Problems on Polygons and Terrains.	International Conference on Computational Science	2003	DBLP DOI BibTeX RDF
1	Ketan Kotecha, Nilesh Gambhava	A Hybrid Genetic Algorithm for Minimum Vertex Cover Problem.	IICAI	2003	DBLP BibTeX RDF
1	Andrzej Lingas, Martin Wahlen	Subexponential-Time Algorithms for Maximum Independent Set and Related Problems on Box Graphs.	COCOON	2003	DBLP DOI BibTeX RDF
1	Martin Grohe	Local Tree-Width, Excluded Minors, and Approximation Algorithms.	Combinatorica	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C83, 05C85, 68W25
1	Xiang-Yang Li, Yu Wang 0003	Simple heuristics and PTASs for intersection graphs in wireless ad hoc networks.	DIAL-M	2002	DBLP DOI BibTeX RDF	disk graphs, wireless ad hoc networks, independent set, PTAS, vertex cover, vertex coloring
1	Irit Dinur, Shmuel Safra	The importance of being biased.	STOC	2002	DBLP DOI BibTeX RDF
1	Jonas Holmerin	Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 - \epsilon. (PDF / PS)	IEEE Conference on Computational Complexity	2002	DBLP DOI BibTeX RDF
1	Jonas Holmerin	Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs.	ICALP	2002	DBLP DOI BibTeX RDF
1	Ulrike Stege, Iris van Rooij, Alexander Hertel, Philipp Hertel	An O(pn + 1.151p)-Algorithm for p-Profit Cover and Its Practical Implications for Vertex Cover.	ISAAC	2002	DBLP DOI BibTeX RDF
1	Paul Renteln	The Hilbert Series of the Face Ring of a Flag Complex.	Graphs and Combinatorics	2002	DBLP DOI BibTeX RDF
1	Oded Goldreich	Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.	Electronic Colloquium on Computational Complexity (ECCC)	2001	DBLP BibTeX RDF
1	Michele Zito	Greedy Algorithms for Minimisation Problems in Random Regular Graphs.	ESA	2001	DBLP DOI BibTeX RDF
1	Jianer Chen, Iyad A. Kanj	On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms.	WG	2001	DBLP DOI BibTeX RDF
1	Jianer Chen, Iyad A. Kanj	On Approximating Minimum Vertex Cover for Graphs with Perfect Matching.	ISAAC	2000	DBLP DOI BibTeX RDF
1	Andrea E. F. Clementi, Luca Trevisan	Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints.	Theor. Comput. Sci.	1999	DBLP DOI BibTeX RDF
1	Paola Alimonti, Viggo Kann	Hardness of Approximating Problems on Cubic Graphs.	CIAC	1997	DBLP DOI BibTeX RDF
1	Andrea E. F. Clementi, Luca Trevisan	Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints	Electronic Colloquium on Computational Complexity (ECCC)	1996	DBLP BibTeX RDF
1	Pierluigi Crescenzi, Luca Trevisan	On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem.	ITA	1996	DBLP BibTeX RDF
1	Yung-Ming Fang, D. F. Wong	Multiplexor Network Generation in High Level Synthesis. (PDF / PS)	ICCD	1996	DBLP DOI BibTeX RDF	High Level Synthesis
1	Pierluigi Crescenzi, Luca Trevisan	Minimum Vertex Cover, Distributed Decision-Making, and Communication Complexity (Extended Abstract).	WG	1994	DBLP DOI BibTeX RDF
1	Vassilis Zissimopoulos, Vangelis Th. Paschos, Ferhan Pekergin	On the Approximation of NP-Complete Problems by Using the Boltzmann Machine Method: The Cases of Some Covering and Packing Problems.	IEEE Trans. Computers	1991	DBLP DOI BibTeX RDF	Boltzmann machine method, minimum vertex cover, computational complexity, parallel architectures, approximation, neural nets, NP-complete problems, heuristic programming, covering, clique, combinatorial mathematics, optimal solutions, maximum independent set, set partitioning, packing problems, minimum set cover
1	Zhugou Mo, Kenneth Williams	Algorithms on Block-Complete Graphs.	Great Lakes Computer Science Conference	1989	DBLP DOI BibTeX RDF