Search results for "independent set"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Bahram Alidaee, Gary A. Kochenberger, Haibo Wang	Simple and fast surrogate constraint heuristics for the maximum independent set problem.	J. Heuristics	2008	DBLP DOI BibTeX RDF	Surrogate constraints, Heuristics, Maximum independent set
3	Nicholas Nash, Sylvain Lelait, David Gregg	Efficiently implementing maximum independent set algorithms on circle graphs.	ACM Journal of Experimental Algorithmics	2008	DBLP DOI BibTeX RDF	Circle graph, maximum stable set, maximum independent set
3	Vladimir E. Alekseev, Vadim V. Lozin, Dmitriy S. Malyshev, Martin Milanic	The Maximum Independent Set Problem in Planar Graphs.	MFCS	2008	DBLP DOI BibTeX RDF	maximum independent set problem, hereditary classes, planar graphs
3	Peng Wang, Stephan Bohacek	On the practical complexity of solving the maximum weighted independent set problem for optimal scheduling in wireless networks.	WICON	2008	DBLP DOI BibTeX RDF	wireless mesh network, optimal scheduling, maximum weighted independent set
3	Beat Gfeller, Elias Vicari	A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs.	PODC	2007	DBLP DOI BibTeX RDF	distributed algorithms, maximal independent set, ad hoc sensor networks
3	Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch	Measure and conquer: a simple O(20.288n) independent set algorithm.	SODA	2006	DBLP DOI BibTeX RDF	exponential-time exact algorithms, independent set problem, NP-hard problems, algorithms and data structures
3	Vadim V. Lozin, Martin Milanic	A polynomial algorithm to find an independent set of maximum weight in a fork-free graph.	SODA	2006	DBLP DOI BibTeX RDF	polynomial-time algorithm, independent set
3	Dechang Chen, Xilong Mao, Xia Fei, Kai Xing, Fang Liu, Min Song	A Convex-Hull Based Algorithm to Connect the Maximal Independent Set in Unit-Disk Graphs.	WASA	2006	DBLP DOI BibTeX RDF	Ad hoc and sensor networks, connected dominating set, maximal independent set
3	Ji-Cherng Lin, Tetz C. Huang	An Efficient Fault-Containing Self-Stabilizing Algorithm for Finding a Maximal Independent Set.	IEEE Trans. Parallel Distrib. Syst.	2003	DBLP DOI BibTeX RDF	Central demon, single transient fault, restrictions on guard conditions, primary variables, auxiliary secondary variables, stabilization time, contamination number, maximal independent set, fault-containment
3	Giuliano Grossi, Roberto Posenato	A Distributed Algorithm for Max Independent Set Problem Based on Hopfield Networks.	WIRN	2002	DBLP DOI BibTeX RDF	Max Independent Set, synchronous distributed algorithms, Hopfield networks
3	Vangelis Th. Paschos	On-line independent set by coloring vertices.	Operational Research	2001	DBLP DOI BibTeX RDF	On-line computation, Approximation algorithm, Coloring, Independent set
3	Afonso Ferreira, Nicolas Schabanel	A Randomized BSP/CGM Algorithm for the Maximal Independent Set Problem.	ISPAN	1999	DBLP DOI BibTeX RDF	Coarse-Grained Models, p-quantiles Search, Parallel Algorithms, Randomized Algorithms, Sorting, Graph Algorithms, Maximal Independent Set, BSP, CGM
3	Mauricio G. C. Resende, Thomas A. Feo, Stuart H. Smith	Algorithm 787: Fortran Subroutines for Approximate Solution of Maximum Independent Set Problems Using GRASP.	ACM Trans. Math. Softw.	1998	DBLP DOI BibTeX RDF	combinatorial optimization, FORTRAN, local search, GRASP, maximum independent set, maximum clique, Fortran subroutines
3	Ingo Schiermeyer	Approximating Maximum Independent Set in k-Clique-Free Graphs.	APPROX	1998	DBLP DOI BibTeX RDF	k-Clique, Algorithm, Complexity, Approximation, Graph, Maximum Independent Set
2	Kenny Erleben	Maximal independent set graph partitions for representations of body-centered cubic lattices.	The Visual Computer	2009	DBLP DOI BibTeX RDF	Coarsening, Body-centered cubic lattice, Graph, Refinement
2	José Soares, Marco A. Stefanes	Algorithms for Maximum Independent Set in Convex Bipartite Graphs.	Algorithmica	2009	DBLP DOI BibTeX RDF	Convex bipartite graphs, BSP/CGM algorithms, Parallel algorithm, Independent sets
2	Marcello Pelillo	Heuristics for Maximum Clique and Independent Set.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Algorithms, Heuristics, Independent set, Clique
2	Parinya Chalermsook, Julia Chuzhoy	Maximum independent set of rectangles.	SODA	2009	DBLP DOI BibTeX RDF
2	Geir Agnarsson, Magnús M. Halldórsson, Elena Losievskaja	SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs.	ICALP	2009	DBLP DOI BibTeX RDF
2	Timothy M. Chan, Sariel Har-Peled	Approximation algorithms for maximum independent set of pseudo-disks.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	approximation., local search
2	Daniel Díaz-Pernil, Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustin Riscos-Núñez	Solving the Independent Set Problem by Using Tissue-Like P Systems with Cell Division.	IWINAC	2009	DBLP DOI BibTeX RDF
2	Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch	A measure & conquer approach for the analysis of exact algorithms.	J. ACM	2009	DBLP DOI BibTeX RDF	Dominating set, exact algorithm, independent set
2	Chris Calabro, Ramamohan Paturi	k-SAT Is No Harder Than Decision-Unique-k-SAT.	CSR	2009	DBLP DOI BibTeX RDF	unique satisfiability, independent set, quantified Boolean formulas, hitting set, k-SAT, exponential complexity
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	Kai Plociennik	Approximating Independent Set and Coloring in Random Uniform Hypergraphs.	MFCS	2008	DBLP DOI BibTeX RDF
2	Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos	An O*(1.0977n) Exact Algorithm for max independent set in Sparse Graphs.	IWPEC	2008	DBLP DOI BibTeX RDF
2	Diogo Vieira Andrade, Mauricio G. C. Resende, Renato Fonseca F. Werneck	Fast Local Search for the Maximum Independent Set Problem.	WEA	2008	DBLP DOI BibTeX RDF
2	Andreas Brandstädt, Tilo Klembt, Vadim V. Lozin, Raffaele Mosca	Independent Sets of Maximum Weight in Apple-Free Graphs.	ISAAC	2008	DBLP DOI BibTeX RDF	clique separators, apple-free graphs, polynomial-time algorithm, Maximum independent set, modular decomposition, claw-free graphs
2	Youmei Li, Zongben Xu, Feilong Cao	An Improvement to Ant Colony Optimization Heuristic.	ISNN	2008	DBLP DOI BibTeX RDF	Hopfield discrete neural network, Ant colony optimization, Maximum independent set
2	Xianyue Li, Xiaofeng Gao, Weili Wu	A Better Theoretical Bound to Approximate Connected Dominating Set in Unit Disk Graph.	WASA	2008	DBLP DOI BibTeX RDF	Minimum Independent Set, Connected Dominating Set, Unit Disk Graph
2	Egbert Mujuni	Parameterized Algorithms in Smooth 4-Regular Hamiltonian Graphs.	Mathematics in Computer Science	2008	DBLP DOI BibTeX RDF	Algorithm, graph coloring, independent set, parameterized complexity
2	Gary A. Kochenberger, Bahram Alidaee, Fred Glover, Haibo Wang	An effective modeling and solution approach for the generalized independent set problem.	Optimization Letters	2007	DBLP DOI BibTeX RDF
2	Naoki Matsumaru, Thorsten Lenser, Thomas Hinze, Peter Dittrich	Toward Organization-Oriented Chemical Programming: A Case Study with the Maximal Independent Set Problem.	Advances in Biologically Inspired Information Systems	2007	DBLP DOI BibTeX RDF
2	Xin Han, Kazuo Iwama, Rolf Klein, Andrzej Lingas	Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs.	AAIM	2007	DBLP DOI BibTeX RDF
2	Petteri Kaski, Aleksi Penttinen, Jukka Suomela	Coordinating Concurrent Transmissions: A Constant-Factor Approximation of Maximum-Weight Independent Set in Local Conflict Graphs.	ADHOC-NOW	2007	DBLP DOI BibTeX RDF	Geometric graphs, maximum-weight independent set, radio interference
2	Vadim V. Lozin, Martin Milanic	Maximum independent sets in graphs of low degree.	SODA	2007	DBLP DOI BibTeX RDF	NP-hardness, polynomial-time algorithm, independent set
2	My T. Thai, Feng Wang 0002, Dan Liu, Shiwei Zhu, Ding-Zhu Du	Connected Dominating Sets in Wireless Networks with Different Transmission Ranges.	IEEE Trans. Mob. Comput.	2007	DBLP DOI BibTeX RDF	disk graph, wireless network, Connected dominating set, independent set, virtual backbone
2	Jizhen Zhao, Dongsheng Che, Liming Cai	Comparative Pathway Prediction Via Unified Graph Modeling of Genomic Structure Information.	ISBRA	2007	DBLP DOI BibTeX RDF	Pathway prediction, protein-DNA interaction, operon, independent set, clique, tree decomposition
2	Xinshun Xu, Jun Ma, Hua Wang	An Improved Simulated Annealing Algorithm for the Maximum Independent Set Problem.	ICIC	2006	DBLP DOI BibTeX RDF
2	Jan Kára, Jan Kratochvíl	Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs.	IWPEC	2006	DBLP DOI BibTeX RDF
2	Stefan Porschen	Counting All Solutions of Minimum Weight Exact Satisfiability.	CIAC	2006	DBLP DOI BibTeX RDF	Minimum weight exact satisfiability, minimum weight set partition, counting problem, maximum weight independent set
2	Martin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro	Lower Bounds for Clear Transmissions in Radio Networks.	LATIN	2006	DBLP DOI BibTeX RDF	Station selection, Wake up, Weak Sensor Model, ACM-class: F.2.2, Sensor network, Ad-hoc network, Lower bound, Broadcast, Dominating set, Leader election, Radio network, Maximal independent set, Contention resolution, Random geometric graphs
2	Martin Fürer	A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs.	LATIN	2006	DBLP DOI BibTeX RDF	exponential time algorithm, NP-hard, Maximum independent set, sparse graph
2	Mathieu Couture, Michel Barbeau, Prosenjit Bose, Evangelos Kranakis	Incremental Construction of k-Dominating Sets in Wireless Sensor Networks.	OPODIS	2006	DBLP DOI BibTeX RDF	fault-tolerance, approximation algorithms, distributed algorithms, dominating set, unit disk graph, maximal independent set
2	Akihisa Kako, Takao Ono, Tomio Hirata, Magnús M. Halldórsson	Approximation Algorithms for the Weighted Independent Set Problem.	WG	2005	DBLP DOI BibTeX RDF
2	Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, Roger Wattenhofer	Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs.	DISC	2005	DBLP DOI BibTeX RDF
2	Uriel Feige, Eran Ofek	Finding a Maximum Independent Set in a Sparse Random Graph.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
2	Fabian Kuhn, Tim Nieberg, Thomas Moscibroda, Roger Wattenhofer	Local approximation schemes for ad hoc and sensor networks.	DIALM-POMC	2005	DBLP DOI BibTeX RDF	distributed algorithm, approximation, wireless ad hoc networks, maximum independent set, minimum dominating set
2	B. Paul, S. V. Rao, S. Nandi	An Efficient Distributed Algorithm for Finding Virtual Backbones in Wireless Ad-Hoc Networks.	HiPC	2005	DBLP DOI BibTeX RDF	MANET, connected dominating set, independent set
2	Marc Demange, Bernard Kouakou, Éric Soutif	On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems.	ISAAC	2005	DBLP DOI BibTeX RDF	hereditary property, on-line algorithm, competitivity ratio, independent set
2	Stefan Porschen	On Some Weighted Satisfiability and Graph Problems.	SOFSEM	2005	DBLP DOI BibTeX RDF	(weighted) exact satisfiability, not-all-equal satisfiability, NP-completeness, exact algorithm, counting problem, maximum weight independent set
2	Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara	Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs.	WG	2005	DBLP DOI BibTeX RDF	# P-completeness, NP-completeness, polynomial time algorithm, enumeration, independent set, Chordal graph, counting
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	Valmir C. Barbosa, Luciana C. D. Campos	A Novel Evolutionary Formulation of the Maximum Independent Set Problem.	J. Comb. Optim.	2004	DBLP DOI BibTeX RDF	genetic algorithms, evolutionary algorithms, maximum independent sets
2	Pankaj K. Agarwal, Nabil H. Mustafa	Independent Set of Intersection Graphs of Convex Objects in 2D.	SWAT	2004	DBLP DOI BibTeX RDF
2	Miroslav Chlebík, Janka Chlebíková	On Approximability of the Independent Set Problem for Low Degree Graphs.	SIROCCO	2004	DBLP DOI BibTeX RDF
2	Liane Lewin-Eytan, Joseph Naor, Ariel Orda	Admission Control in Networks with Advance Reservations.	Algorithmica	2004	DBLP DOI BibTeX RDF	Line network, Axis parallel rectangles, Approximation algorithms, Independent set, Advance reservations, Local ratio
2	Jens Gustedt, Jan Arne Telle	A Work-Optimal Coarse-Grained PRAM Algorithm for Lexicographically First Maximal Independent Set.	ICTCS	2003	DBLP DOI BibTeX RDF
2	Pavel A. Borisovsky, Marina S. Zavolovskaya	Experimental Comparison of Two Evolutionary Algorithms for the Independent Set Problem.	EvoWorkshops	2003	DBLP DOI BibTeX RDF
2	Andrzej Lingas, Martin Wahlen	Subexponential-Time Algorithms for Maximum Independent Set and Related Problems on Box Graphs.	COCOON	2003	DBLP DOI BibTeX RDF
2	Gabriel Valiente	A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs.	ISAAC	2003	DBLP DOI BibTeX RDF
2	Yll Haxhimusa, Roland Glantz, Walter G. Kropatsch	Constructing Stochastic Pyramids by MIDES - Maximal Independent Directed Edge Set.	GbRPR	2003	DBLP DOI BibTeX RDF	irregular graph pyramids, maximal independent directed edge set, topology preserving contraction, maximal independent set
2	Stéphan Ceroi	A Weighted Version of the Jump Number Problem on Two-Dimensional Orders is NP-Complete.	Order	2003	DBLP DOI BibTeX RDF	jump number, dimension, maximal independent set
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	Sergiy Butenko, Panos M. Pardalos, Ivan Sergienko, Vladimir Shylo, Petro Stetsyuk	Finding maximum independent sets in graphs arising from coding theory.	SAC	2002	DBLP DOI BibTeX RDF	codes for Z-channel, deletion-correcting codes, transposition-correction codes, maximum independent set
2	Piotr Berman	A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs.	SWAT	2000	DBLP DOI BibTeX RDF
2	Tao Jiang, Guohui Lin, Bin Ma, Kaizhong Zhang	The Longest Common Subsequence Problem for Arc-Annotated Sequences.	CPM	2000	DBLP DOI BibTeX RDF	Sequence annotation, approximation algorithm, dynamic programming, longest common subsequence, maximum independent set, MAX SNP-hard
2	G. Sajith, Sanjeev Saxena	Optimal Sublogarithmic Time Parallel Algorithms on Rooted Forests.	Algorithmica	2000	DBLP DOI BibTeX RDF	CRCW model, Tree colouring, Parallel algorithms, Optimal algorithms, Maximal independent set
2	Bram Verweij, Karen Aardal	An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling.	ESA	1999	DBLP DOI BibTeX RDF
2	Magnús M. Halldórsson	Approximations of Weighted Independent Set and Hereditary Subset Problems.	COCOON	1999	DBLP DOI BibTeX RDF
2	H. Y. Lau, H. F. Ting	The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set.	COCOON	1999	DBLP DOI BibTeX RDF
2	Piotr Berman, Marek Karpinski	On Some Tighter Inapproximability Results (Extended Abstract).	ICALP	1999	DBLP DOI BibTeX RDF	Approximation Hardness, Bounded Dependency Satisfiability, Breakpoint Graphs, Node Cover, Approximation Algorithms, Independent Set, MAX-CUT, Sorting by Reversals
2	Dimitrios Kagaris, Spyros Tragoudas	Maximum independent sets on transitive graphs and their applications in testing and CAD.	ICCAD	1997	DBLP DOI BibTeX RDF	VLSI contexts, physical design automation, scheduling, VLSI, high level synthesis, polynomial time algorithm, CAD tool, channel routing, maximum weighted independent set, path delay fault testing, transitive graphs
2	Ryuhei Uehara	A Measure of Parallelization for the Lexicographically First Maximal Subgraph Problems.	WG	1997	DBLP DOI BibTeX RDF	the lexicographically first maximal independent set problem, the lexicographically first maximal subgraph problems, Analysis of algorithms, P-completeness, NC algorithms
2	Eric Bach, Anne Condon, Elton Glaser, Celena Tanguay	DNA Models and Algorithms for NP-complete Problems. (PDF / PS)	IEEE Conference on Computational Complexity	1996	DBLP DOI BibTeX RDF	3Sat, 3-Coloring, Independent Set problem, DNA algorithms, genetic algorithms, computational complexity, search problems, DNA computing, DNA computation, NP-complete problems, search algorithms, NP-hard problems
2	Y. Daniel Liang, Chongkye Rhee	Linear Algorithms for Two Independent Set Problems in Permutation Graphs.	ACM Conference on Computer Science	1994	DBLP DOI BibTeX RDF	minimum weight independent dominating set, maximum weight independent set, permutation graphs
2	Deborah Joseph, Joao Meidanis, Prasoon Tiwari	Determining DNA Sequence Similarity Using Maximum Independent Set Algorithms for Interval Graphs.	SWAT	1992	DBLP DOI BibTeX RDF
2	Piotr Berman, Georg Schnitger	On the Complexity of Approximating the Independent Set Problem.	STACS	1989	DBLP DOI BibTeX RDF
2	Wen-Lian Hsu	The coloring and maximum independent set problems on planar perfect graphs.	J. ACM	1988	DBLP DOI BibTeX RDF
2	Richard M. Karp, Avi Wigderson	A Fast Parallel Algorithm for the Maximal Independent Set Problem	J. ACM	1985	DBLP DOI BibTeX RDF
2	C. E. Veni Madhavan	Approximation Algorithm for Maximum Independent Set in Planar Tiangle-Free Graphs.	FSTTCS	1984	DBLP DOI BibTeX RDF
1	Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos, O. Pottié	The max quasi-independent set problem.	J. Comb. Optim.	2012	DBLP DOI BibTeX RDF
1	Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij	Fast Algorithms for max independent set.	Algorithmica	2012	DBLP DOI BibTeX RDF
1	Qinghua Wu, Jin-Kao Hao	Coloring large graphs based on independent set extraction.	Computers & OR	2012	DBLP DOI BibTeX RDF
1	Stasys Jukna	Independent set problem for individual graphs has small communication complexity	CoRR	2012	DBLP BibTeX RDF
1	Guy E. Blelloch, Jeremy T. Fineman, Julian Shun	Greedy Sequential Maximal Independent Set and Matching are Parallel on Average	CoRR	2012	DBLP BibTeX RDF
1	Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider	Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set	CoRR	2012	DBLP BibTeX RDF
1	David Bergman, André A. Ciré, Willem Jan van Hoeve, John N. Hooker	Variable Ordering for the Application of BDDs to the Maximum Independent Set Problem.	CPAIOR	2012	DBLP DOI BibTeX RDF
1	Yury L. Orlovich, Jacek Blazewicz, Alexandre Dolgui, Gerd Finke, Valery S. Gordon	On the complexity of the independent set problem in triangle graphs.	Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Per Austrin, Subhash Khot, Muli Safra	Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.	Theory of Computing	2011	DBLP DOI BibTeX RDF
1	Jiakai Li, Gürsel Serpen	TOSSIM simulation of wireless sensor network serving as hardware platform for Hopfield neural net configured for max independent set.	Procedia CS	2011	DBLP DOI BibTeX RDF
1	Jiakai Li, Gürsel Serpen	nesC-TinyOS model for parallel and distributed computation of max independent set by Hopfield network on wireless sensor network.	Procedia CS	2011	DBLP DOI BibTeX RDF
1	Gürsel Serpen, Jiakai Li	Parallel and distributed computations of maximum independent set by a Hopfield neural net embedded into a wireless sensor network.	Procedia CS	2011	DBLP DOI BibTeX RDF
1	Jonathan Cutler, A. J. Radcliffe	Extremal Problems for Independent Set Enumeration.	Electr. J. Comb.	2011	DBLP BibTeX RDF
1	Filipe Araujo, Jorge Farinha, Patrício Domingues, Gheorghe Cosmin Silaghi, Derrick Kondo	A maximum independent set approach for collusion detection in voting pools.	J. Parallel Distrib. Comput.	2011	DBLP DOI BibTeX RDF
1	Hui-Gui Rong, Hao Chen	An Independent Set Packet Classification Algorithm Using Priority Sorting.	JNW	2011	DBLP DOI BibTeX RDF
1	Vadim E. Levit, Eugen Mandrescu	On the Structure of the Minimum Critical Independent Set of a Graph	CoRR	2011	DBLP BibTeX RDF
1	Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn	Computing a Maximal Independent Set Using Beeps	CoRR	2011	DBLP BibTeX RDF
1	Timothy M. Chan, Sariel Har-Peled	Approximation Algorithms for Maximum Independent Set of Pseudo-Disks	CoRR	2011	DBLP BibTeX RDF
1	Landon Rabern	On hitting all maximum cliques with an independent set.	Journal of Graph Theory	2011	DBLP DOI BibTeX RDF