Search results for "vertex cover"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Matti Åstrand, Jukka Suomela	Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks.	SPAA	2010	DBLP DOI BibTeX RDF	edge packing, distributed algorithm, local algorithm, set cover, vertex cover, anonymous network
3	Krzysztof Onak, Ronitt Rubinfeld	Maintaining a large matching and a small vertex cover.	STOC	2010	DBLP DOI BibTeX RDF	data structures, vertex cover, dynamic algorithms, maximum matching
3	Christoph Ambühl, Monaldo Mastrolilli	Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem.	Algorithmica	2009	DBLP DOI BibTeX RDF	Scheduling, Algorithms, Vertex cover
3	Julián Mestre	A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses.	Algorithmica	2009	DBLP DOI BibTeX RDF	Approximation algorithms, Vertex cover, Primal-dual algorithms
3	Christos Koufogiannakis, Neal E. Young	Distributed and parallel algorithms for weighted vertex cover and other covering problems.	PODC	2009	DBLP DOI BibTeX RDF	distributed covering, distributed vertex cover
3	Volker Turau, Bernd Hauck	A Self-stabilizing Approximation Algorithm for Vertex Cover in Anonymous Networks.	SSS	2009	DBLP DOI BibTeX RDF	distributed algorithms, vertex cover, anonymous networks, self-stabilizing algorithms
3	Sundar Vishwanathan	On hard instances of approximate vertex cover.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	Approximation algorithms, vertex cover
3	Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi	Distributed weighted vertex cover via maximal matchings.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	Approximation algorithms, distributed algorithms, vertex cover, maximal matching
3	Daniel Mölle, Stefan Richter, Peter Rossmanith	Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	Enumerate and expand, Exact algorithms, Vertex cover, Parameterized complexity
3	Zhao Zhang, Xiaofeng Gao, Weili Wu	Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph.	COCOA	2008	DBLP DOI BibTeX RDF	Connected Vertex Cover, Unit Disk Graph
3	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
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
3	Bruno Escoffier, Laurent Gourvès, Jérôme Monnot	Complexity and Approximation Results for the Connected Vertex Cover Problem.	WG	2007	DBLP DOI BibTeX RDF	Connected vertex cover, APX-complete, approximation algorithm, planar graphs, bipartite graphs, chordal graphs
3	Qizhi Fang, Liang Kong	Core Stability of Vertex Cover Games.	WINE	2007	DBLP DOI BibTeX RDF	Vertex cover game, stable core, largeness, exactness, balanced, extendability
3	Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg	Frugality ratios and improved truthful mechanisms for vertex cover.	ACM Conference on Electronic Commerce	2007	DBLP DOI BibTeX RDF	frugality, auctions, vertex cover
3	Maytham Safar, Sami Habib	Hard Constrained Vertex-Cover Communication Algorithm for WSN.	EUC	2007	DBLP DOI BibTeX RDF	discrete space, Wireless sensor network, optimization, communication, vertex cover, evolutionary approach
3	Refael Hassin, Asaf Levin	The minimum generalized vertex cover problem.	ACM Transactions on Algorithms	2006	DBLP DOI BibTeX RDF	complexity classification, Vertex cover, local-ratio
3	Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, Mauro Sozio	Primal-dual based distributed algorithms for vertex cover with semi-hard capacities.	PODC	2005	DBLP DOI BibTeX RDF	approximation algorithms, distributed algorithms, vertex cover, primal-dual algorithms
3	Shyong Jian Shyu, Peng-Yeng Yin, Bertrand M. T. Lin	An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem.	Annals OR	2004	DBLP DOI BibTeX RDF	minimum weight vertex cover, meta-heuristic algorithm, ant colony optimization
3	Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan	An Improved Approximation Algorithm for Vertex Cover with Hard Capacities.	ICALP	2003	DBLP DOI BibTeX RDF	capacitated covering, Approximation algorithms, linear programming, set cover, vertex cover, randomized rounding
3	Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev	A new multilayered PCP and the hardness of hypergraph vertex cover.	STOC	2003	DBLP DOI BibTeX RDF	hypergraph vertex cover, long code, multilayered PCP, hardness of approximation
3	Eran Halperin, Aravind Srinivasan	Improved Approximation Algorithms for the Partial Vertex Cover Problem.	APPROX	2002	DBLP DOI BibTeX RDF	Partial vertex cover, approximation algorithms, semidefinite programming, randomized rounding
2	Holger Dell, Dieter van Melkebeek	Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses.	STOC	2010	DBLP DOI BibTeX RDF	arithmetic progression free sets, hereditary graph properties, vertex deletion problems, satisfiability, kernelization, vertex cover, parameterized complexity, probabilistically checkable proofs, feedback vertex set, sparsification
2	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
2	Carsten Witt	Greedy Local Search and Vertex Cover in Sparse Random Graphs.	TAMC	2009	DBLP DOI BibTeX RDF
2	Jirí Fiala, Petr A. Golovach, Jan Kratochvíl	Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover.	TAMC	2009	DBLP DOI BibTeX RDF
2	Peter Damaschke	Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover.	IWPEC	2009	DBLP DOI BibTeX RDF
2	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
2	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
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	Fanica Gavril, Alon Itai	Covering a Tree by a Forest.	Graph Theory, Computational Intelligence and Thought	2009	DBLP DOI BibTeX RDF	vertex-cover of a tree by a forest, edge-cover of a tree by a forest, graph algorithms
2	Michael Lampis, Valia Mitsou	The Ferry Cover Problem.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Wolf-goat-cabbage puzzle, Approximation algorithms, Graph algorithms, Vertex cover, Transportation problems
2	Ju Wang, Jonathan C. L. Liu	Uplink relaying in hybrid wireless networks with out-of-cell interference reduction.	Wireless Networks	2009	DBLP DOI BibTeX RDF	Uplink relaying, Out-cell-interference, Wireless network, WLAN, WCDMA, Vertex 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	Guoqiang Bai 0002, Henning Fernau	Constraint Bipartite Vertex Cover: Simpler Exact Algorithms and Implementations.	FAW	2008	DBLP DOI BibTeX RDF
2	Joachim Kneis, Alexander Langer, Peter Rossmanith	Improved Upper Bounds for Partial Vertex Cover.	WG	2008	DBLP DOI BibTeX RDF
2	Andreas Wiese, Evangelos Kranakis	Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs.	DCOSS	2008	DBLP DOI BibTeX RDF
2	Konstantinos Georgiou, Avner Magen, Iannis Tourlakis	Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities.	IPCO	2008	DBLP DOI BibTeX RDF
2	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
2	Venkatesh Raman, Saket Saurabh	Short Cycles Make W -hard Problems Hard: FPT Algorithms for W -hard Problems in Graphs with no Short Cycles.	Algorithmica	2008	DBLP DOI BibTeX RDF	t-vertex cover, Dominating set, Set cover, Independent set, Parameterized complexity
2	Faisal N. Abu-Khzam, Michael R. Fellows, Michael A. Langston, W. Henry Suters	Crown Structures for Vertex Cover Kernelization.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
2	Jiong Guo, Rolf Niedermeier, Sebastian Wernicke	Parameterized Complexity of Vertex Cover Variants.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
2	Noga Alon, Raphael Yuster	Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover.	ESA	2007	DBLP DOI BibTeX RDF
2	Reuven Bar-Yehuda, Guy Flysher, Julián Mestre, Dror Rawitz	Approximation of Partial Capacitated Vertex Cover.	ESA	2007	DBLP DOI BibTeX RDF
2	Pietro Simone Oliveto, Jun He, Xin Yao	Evolutionary algorithms and the Vertex Cover problem.	IEEE Congress on Evolutionary Computation	2007	DBLP DOI BibTeX RDF
2	Eyjolfur Asgeirsson, Clifford Stein	Vertex Cover Approximations on Random Graphs.	WEA	2007	DBLP DOI BibTeX RDF
2	Amos Beimel, Renen Hallak, Kobbi Nissim	Private Approximation of Clustering and Vertex Cover.	TCC	2007	DBLP DOI BibTeX RDF
2	Maytham Safar, Mohammad Taha, Sami Habib	Modeling the Communication Problem in Wireless Sensor Networks as a Vertex Cover.	AICCSA	2007	DBLP DOI BibTeX RDF
2	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
2	Hamed Hatami, Avner Magen, Evangelos Markakis	Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l1 Embeddability of Negative Type Metrics.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
2	Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis	Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy.	FOCS	2007	DBLP DOI BibTeX RDF
2	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
2	Silvia Richter, Malte Helmert, Charles Gretton	A Stochastic Local Search Approach to Vertex Cover.	KI	2007	DBLP DOI BibTeX RDF
2	Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani	A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.	IEEE Conference on Computational Complexity	2007	DBLP DOI BibTeX RDF
2	Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani	Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut.	STOC	2007	DBLP DOI BibTeX RDF	Lovasz-Schrijver hierarchy, approximation algorithms, linear programming, integrality gap
2	Michael Lampis, Valia Mitsou	The Ferry Cover Problem.	FUN	2007	DBLP DOI BibTeX RDF	wolf-goat-cabbage puzzle, approximation algorithms, graph algorithms, vertex cover, transportation problems
2	Christoph Ambühl, Monaldo Mastrolilli	Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem.	ESA	2006	DBLP DOI BibTeX RDF
2	Stephen Gilmour, Mark Dras	Kernelization as Heuristic Structure for the Vertex Cover Problem.	ANTS Workshop	2006	DBLP DOI BibTeX RDF
2	Mingji Xia, Wenbo Zhao	#3-Regular Bipartite Planar Vertex Cover is #P-Complete.	TAMC	2006	DBLP DOI BibTeX RDF
2	Jianer Chen, Iyad A. Kanj, Ge Xia	Improved Parameterized Upper Bounds for Vertex Cover.	MFCS	2006	DBLP DOI BibTeX RDF
2	Josep Díaz, Jordi Petit, Dimitrios M. Thilikos	Kernels for the Vertex Cover Problem on the Preferred Attachment Model.	WEA	2006	DBLP DOI BibTeX RDF
2	Daniel Mölle, Stefan Richter, Peter Rossmanith	Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants.	COCOON	2006	DBLP DOI BibTeX RDF
2	Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith	Intuitive Algorithms and t-Vertex Cover.	ISAAC	2006	DBLP DOI BibTeX RDF
2	Iannis Tourlakis	New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy.	IEEE Conference on Computational Complexity	2006	DBLP DOI BibTeX RDF
2	Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb	Private approximation of search problems.	STOC	2006	DBLP DOI BibTeX RDF	private approximation, solution-list algorithm, vertex cover, secure computation
2	Benny Chor, Tamir Tuller	Finding a maximum likelihood tree is hard.	J. ACM	2006	DBLP DOI BibTeX RDF	approximate vertex cover, tree reconstruction, Maximum likelihood, maximum parsimony, intractability
2	Tomokazu Imamura, Kazuo Iwama	Approximating vertex cover on dense graphs.	SODA	2005	DBLP DOI BibTeX RDF
2	Zhiping Cai, Jianping Yin, Xianghui Liu, Shaohe Lv	An Approximation Algorithm for Weak Vertex Cover Problem in Network Management.	AAIM	2005	DBLP DOI BibTeX RDF
2	George Karakostas	A Better Approximation Ratio for the Vertex Cover Problem.	ICALP	2005	DBLP DOI BibTeX RDF
2	Eyjolfur Asgeirsson, Clifford Stein	Vertex Cover Approximations: Experiments and Observations.	WEA	2005	DBLP DOI BibTeX RDF
2	Jiong Guo, Rolf Niedermeier, Sebastian Wernicke	Parameterized Complexity of Generalized Vertex Cover Problems.	WADS	2005	DBLP DOI BibTeX RDF
2	Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi	Distributed Weighted Vertex Cover via Maximal Matchings.	COCOON	2005	DBLP DOI BibTeX RDF
2	Faisal N. Abu-Khzam, Michael A. Langston, W. Henry Suters	Fast, effective vertex cover kernelization: a tale of two algorithms.	AICCSA	2005	DBLP DOI BibTeX RDF
2	Julián Mestre	A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
2	Iannis Tourlakis	Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
2	Jun Kiniwa	Approximation of Self-stabilizing Vertex Cover Less Than 2.	Self-Stabilizing Systems	2005	DBLP DOI BibTeX RDF
2	Jianer Chen, Iyad A. Kanj, Ge Xia	Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems.	Algorithmica	2005	DBLP DOI BibTeX RDF	Exact algorithm, Independent set, Vertex cover, Parameterized algorithm
2	Vic Grout	Principles of Cost Minimisation in Wireless Networks.	J. Heuristics	2005	DBLP DOI BibTeX RDF	minimum connected vertex cover problem, node constraints, edge constraints, path constraints, load constraints, add algorithm, drop algorithm, wireless networks
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	Zhiyun Chen, Huiqin Qu, Mingming Lu, Hong Zhu	A Probabilistic Parameterized Algorithm for Vertex Cover in Sticker Model.	IPDPS	2004	DBLP DOI BibTeX RDF
2	L. Sunil Chandran, Fabrizio Grandoni	Refined Memorisation for Vertex Cover.	IWPEC	2004	DBLP DOI BibTeX RDF
2	Frank K. H. A. Dehne, Michael R. Fellows, Frances A. Rosamond, Peter Shaw	Greedy Localization, Iterative Compression, Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting, and a Novel 2k Kernelization for Vertex Cover.	IWPEC	2004	DBLP DOI BibTeX RDF
2	Erik J. Hanashiro, Henrique Mongelli, Siang W. Song	Efficient Implementation of the BSP/CGM Parallel Vertex Cover FPT Algorithm.	WEA	2004	DBLP DOI BibTeX RDF
2	Yong Zhang, Hong Zhu	An Approximation Algorithm for Weighted Weak Vertex Cover Problem in Undirected Graphs.	COCOON	2004	DBLP DOI BibTeX RDF
2	Tomokazu Imamura, Kazuo Iwama, Tatsuie Tsukiji	Approximated Vertex Cover for Graphs with Perfect Matchings.	COCOON	2004	DBLP DOI BibTeX RDF
2	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
2	Stefan Porschen, Ewald Speckenmeyer	Worst Case Bounds for Some NP-Complete Modified Horn-SAT Problems.	SAT (Selected Papers	2004	DBLP DOI BibTeX RDF	(hidden) Horn formula, quadratic formula, minimal vertex cover, NP-completeness, satisfiability, fixed-parameter tractability
2	Refael Hassin, Asaf Levin	The Minimum Generalized Vertex Cover Problem.	ESA	2003	DBLP DOI BibTeX RDF
2	Elena Prieto, Christian Sloper	Either/Or: Using Vertex Cover Structure in Designing FPT-Algorithms - The Case of k-Internal Spanning Tree.	WADS	2003	DBLP DOI BibTeX RDF
2	Subhash Khot, Oded Regev	Vertex Cover Might be Hard to Approximate to within 2-\varepsilon.	IEEE Conference on Computational Complexity	2003	DBLP DOI BibTeX RDF
2	James Cheetham, Frank K. H. A. Dehne, Andrew Rau-Chaplin, Ulrike Stege, Peter J. Taillon	A Parallel FPT Application For Clusters.	CCGRID	2003	DBLP DOI BibTeX RDF	Fixed-Parameter Tractatbility, k-Vertex Cover, Computational Biochemistry
2	Moses Charikar	On semidefinite programming relaxations for graph coloring and vertex cover.	SODA	2002	DBLP DOI BibTeX RDF
2	Jonas Holmerin	Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs.	ICALP	2002	DBLP DOI BibTeX RDF
2	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
2	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
2	Jonas Holmerin	Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon.	STOC	2002	DBLP DOI BibTeX RDF
2	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
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
2	Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos	Fast Fixed-Parameter Tractable Algorithms for Nontrivial Generalizations of Vertex Cover.	WADS	2001	DBLP DOI BibTeX RDF
2	Rajiv Gandhi, Samir Khuller, Aravind Srinivasan	Approximation Algorithms for Partial Covering Problems.	ICALP	2001	DBLP DOI BibTeX RDF	Approximation algorithms, set cover, vertex cover, randomized rounding, primal-dual methods, partial covering