Search results for "Independent Set problem"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
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	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
2	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
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	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	Xinshun Xu, Jun Ma, Hua Wang	An Improved Simulated Annealing Algorithm for the Maximum Independent Set Problem.	ICIC	2006	DBLP DOI BibTeX RDF
2	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
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	Miroslav Chlebík, Janka Chlebíková	On Approximability of the Independent Set Problem for Low Degree Graphs.	SIROCCO	2004	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	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
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
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	Stasys Jukna	Independent set problem for individual graphs has small communication complexity	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	Glaydston Mattos Ribeiro, Geraldo R. Mauri, Luiz Antonio Nogueira Lorena	A lagrangean decomposition for the maximum independent set problem applied to map labeling.	Operational Research	2011	DBLP DOI BibTeX RDF
1	Piotr Borowiecki, Frank Göring	GreedyMAX-type Algorithms for the Maximum Independent Set Problem.	SOFSEM	2011	DBLP DOI BibTeX RDF
1	Zhen Cheng, Jianhua Xiao	Implementation of Maximum Independent Set Problem by Algorithmic Tile Self-Assembly.	BIC-TA	2011	DBLP DOI BibTeX RDF
1	Vadim V. Lozin, Martin Milanic	On the Maximum Independent Set Problem in Subclasses of Planar Graphs.	J. Graph Algorithms Appl.	2010	DBLP BibTeX RDF
1	Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos, O. Pottié	The max quasi-independent set Problem.	CSR	2010	DBLP DOI BibTeX RDF
1	David Gamarnik, David Goldberg, Theophane Weber	PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs.	SODA	2010	DBLP BibTeX RDF
1	Konrad Dabrowski, Vadim V. Lozin, Haiko Müller, Dieter Rautenbach	Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes.	IWOCA	2010	DBLP DOI BibTeX RDF
1	Martin Milanic, Jérôme Monnot	The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes.	Electronic Notes in Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Vadim V. Lozin	Parameterized complexity of the maximum independent set problem and the speed of hereditary properties.	Electronic Notes in Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Akihisa Kako, Takao Ono, Tomio Hirata, Magnús M. Halldórsson	Approximation algorithms for the weighted independent set problem in sparse graphs.	Discrete Applied Mathematics	2009	DBLP DOI BibTeX RDF
1	Saeed Mehrabi, Abbas Mehrabi, Ali D. Mehrabi	A New Hybrid Genetic Algorithm for Maximum Independent Set Problem.	ICSOFT	2009	DBLP BibTeX RDF
1	Navid Nasr Esfahani, Parisa Mazrooei, Kaveh Mahdaviani, Behnaz Omoomi	A note on the P-time algorithms for solving the maximum independent set problem.	DMO	2009	DBLP DOI BibTeX RDF
1	Vadim V. Lozin	A Note on the Parameterized Complexity of the Maximum Independent Set Problem.	CTW	2009	DBLP BibTeX RDF
1	Parinya Chalermsook, Julia Chuzhoy	Maximum independent set of rectangles.	SODA	2009	DBLP DOI BibTeX RDF
1	Mei-Fang Chiang, Takumi Okamoto, Takeshi Yoshimura	Lagrangian relaxation based register placement for high-performance circuits.	ISQED	2009	DBLP DOI BibTeX RDF
1	Iyad A. Kanj, Dieter Kratsch	Convex Recoloring Revisited: Complexity and Exact Algorithms.	COCOON	2009	DBLP DOI BibTeX RDF
1	Imran A. Pirwani	Shifting Strategy for Geometric Graphs without Geometry.	ISAAC	2009	DBLP DOI BibTeX RDF
1	Hauke Tönnies	An Evolutionary Graph Transformation System as a Modelling Framework for Evolutionary Algorithms.	KI	2009	DBLP DOI BibTeX RDF
1	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
1	Patrick Briest	Uniform Budgets and the Envy-Free Pricing Problem.	ICALP	2008	DBLP DOI BibTeX RDF
1	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
1	Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh	Iterative Compression and Exact Algorithms.	MFCS	2008	DBLP DOI BibTeX RDF
1	Andreas Brandstädt, Chính T. Hoàng	Maximum Induced Matchings for Chordal Graphs in Linear Time.	Algorithmica	2008	DBLP DOI BibTeX RDF	Maximum induced matchings, Perfect elimination order, Lexicographic breadth-first search, Chordal graphs, Linear time algorithm
1	Sergiy Butenko, Svyatoslav Trukhanov	Using critical sets to solve the maximum independent set problem.	Oper. Res. Lett.	2007	DBLP DOI BibTeX RDF
1	Stefan Porschen	On generalizations of the shadow independent set problem.	Discrete Mathematics	2007	DBLP DOI BibTeX RDF
1	Anatoly D. Plotnikov	Experimental Algorithm for the Maximum Independent Set Problem	CoRR	2007	DBLP BibTeX RDF
1	Omar Kettani	An algorithm for solving the Independent Set problem	CoRR	2007	DBLP BibTeX RDF
1	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
1	Vadim V. Lozin, Martin Milanic	On the maximum independent set problem in subclasses of planar and more general graphs.	CTW	2007	DBLP BibTeX RDF
1	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
1	S. Jamaloddin Golestani, Rajeev Rastogi, Mark A. Smith	Optimal Scheduling for Dynamic Channel Allocation in Wireless LANs.	COMSWARE	2007	DBLP DOI BibTeX RDF
1	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
1	Nazim Ashraf, Imran N. Junejo, Hassan Foroosh	Near-Optimal Mosaic Selection for Rotating and Zooming Video Cameras.	ACCV	2007	DBLP DOI BibTeX RDF
1	Zhixiang Chen, Bin Fu, Jinhui Xu, Bo-Ting Yang, Zhiyu Zhao, Binhai Zhu	Non-breaking Similarity of Genomes with Gene Repetitions.	CPM	2007	DBLP DOI BibTeX RDF
1	Peter J. Taillon	Distributed Memorization for the k -Vertex CoverProblem.	ISPA	2007	DBLP DOI BibTeX RDF
1	Li Pan, Weidong Zhao, Zhicheng Wang, Gang Wei, Shumei Wang	On Computation Complexity of the Concurrently Enabled Transition Set Problem.	TAMC	2007	DBLP DOI BibTeX RDF
1	Joe Dundas, T. Andrew Binkowski, Bhaskar DasGupta, Jie Liang	Topology Independent Protein Structural Alignment.	WABI	2007	DBLP DOI BibTeX RDF
1	Magnús M. Halldórsson, Elena Losievskaja	Independent Sets in Bounded-Degree Hypergraphs.	WADS	2007	DBLP DOI BibTeX RDF
1	Klaus Jansen	Approximation Algorithms for Geometric Intersection Graphs.	WG	2007	DBLP DOI BibTeX RDF
1	Paul Beame, Russell Impagliazzo, Ashish Sabharwal	The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs.	Computational Complexity	2007	DBLP DOI BibTeX RDF	Subject classification. 03F20, 68Q17
1	Igor Razgon	A Faster Solving of the Maximum Independent Set Problem for Graphs with Maximal Degree 3.	ACiD	2006	DBLP BibTeX RDF
1	Arist Kojevnikov, Alexander S. Kulikov	A new approach to proving upper bounds for MAX-2-SAT.	SODA	2006	DBLP DOI BibTeX RDF
1	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
1	Alex Samorodnitsky, Luca Trevisan	Gowers uniformity, influence of variables, and PCPs.	STOC	2006	DBLP DOI BibTeX RDF	influence of variables, probabilistically checkable proofs, linearity test
1	L. Sunil Chandran, Naveen Sivadasan	Geometric Representation of Graphs in Low Dimension.	COCOON	2006	DBLP DOI BibTeX RDF
1	Jan Kára, Jan Kratochvíl	Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs.	IWPEC	2006	DBLP DOI BibTeX RDF
1	Bin Fu	Theory and Application of Width Bounded Geometric Separator.	STACS	2006	DBLP DOI BibTeX RDF
1	Christian Bessière, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh	Filtering Algorithms for the NValueConstraint.	Constraints	2006	DBLP DOI BibTeX RDF	NValue constraint, AtleastNValue, AtMostNValue, NP-hard, pruning, global constraints, linear relaxation
1	Deepak Warrier, Wilbert E. Wilhelm, Jeffrey S. Warren, Illya V. Hicks	A branch-and-price approach for the maximum weight independent set problem.	Networks	2005	DBLP DOI BibTeX RDF
1	Pino Caballero-Gil	Zero-Knowledge Proof for the Independent Set Problem.	IEICE Transactions	2005	DBLP DOI BibTeX RDF
1	Weng-Long Chang, Minyi Guo, Jesse Wu	Solving the Independent-set Problem in a Dna-based Supercomputer Model.	Parallel Processing Letters	2005	DBLP DOI BibTeX RDF
1	Xiaoyong Tang, Hai Zhou, Prithviraj Banerjee	Leakage power optimization with dual-Vth library in high-level synthesis.	DAC	2005	DBLP DOI BibTeX RDF	dual-Vth, optimization, high-level synthesis, leakage power
1	Miroslav Chlebík, Janka Chlebíková	Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes.	SODA	2005	DBLP DOI BibTeX RDF
1	Gregory Gutin, Arash Rafiey, Anders Yeo, Michael Tso	Level of Repair Analysis and Minimum Cost Homomorphisms of Graphs.	AAIM	2005	DBLP DOI BibTeX RDF
1	Christian Bessière, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh	Filtering Algorithms for the NValue Constraint.	CPAIOR	2005	DBLP DOI BibTeX RDF
1	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
1	Marc Demange, Vangelis Th. Paschos	Improved Approximations for Weighted and Unweighted Graph Problems.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
1	Tamás Fleiner, András Frank, Satoru Iwata	A constrained independent set problem for matroids.	Oper. Res. Lett.	2004	DBLP DOI BibTeX RDF
1	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
1	Xinshun Xu, Zheng Tang, Jiahai Wang	An improved transiently chaotic neural network for the maximum independent set problem.	Int. J. Neural Syst.	2004	DBLP DOI BibTeX RDF
1	Jochen Alber, Jirí Fiala	Geometric separation and exact solutions for the parameterized independent set problem on disk graphs.	J. Algorithms	2004	DBLP DOI BibTeX RDF
1	Sun-Yuan Hsieh	Characterization of Efficiently Parallel Solvable Problems on a Class of Decomposable Graphs.	International Conference on Computational Science	2004	DBLP DOI BibTeX RDF
1	Tim Nieberg, Johann Hurink, Walter Kern	A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs.	WG	2004	DBLP DOI BibTeX RDF
1	Valmir C. Barbosa, Luciana C. D. Campos	A novel evolutionary formulation of the maximum independent set problem	CoRR	2003	DBLP BibTeX RDF
1	Shuichi Sakai, Mitsunori Togasaki, Koichi Yamazaki	A note on greedy algorithms for the maximum weighted independent set problem.	Discrete Applied Mathematics	2003	DBLP DOI BibTeX RDF
1	Vladimir E. Alekseev	On easy and hard hereditary classes of graphs with respect to the independent set problem.	Discrete Applied Mathematics	2003	DBLP DOI BibTeX RDF
1	Anita Saha, Madhumangal Pal	Maximum weight k-independent set problem on permutation graphs.	Int. J. Comput. Math.	2003	DBLP DOI BibTeX RDF
1	Gabriel Valiente	A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs.	ISAAC	2003	DBLP DOI BibTeX RDF
1	Niwat Waropus, Rajendar Koltur, Malgorzata Chrzanowska-Jeske	Graph-based approach to evaluate net routability of a floorplan.	ISCAS	2003	DBLP DOI BibTeX RDF
1	Roland Glantz, Marcello Pelillo	Graph Polynomials, Principal Piovoting, and Maximum Independent Sets.	GbRPR	2003	DBLP DOI BibTeX RDF
1	Jens Gustedt, Jan Arne Telle	A Work-Optimal Coarse-Grained PRAM Algorithm for Lexicographically First Maximal Independent Set.	ICTCS	2003	DBLP DOI BibTeX RDF
1	Jianer Chen, Iyad A. Kanj, Ge Xia	Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems.	ISAAC	2003	DBLP DOI BibTeX RDF
1	Artur Czumaj, Andrzej Lingas, Johan Nilsson	Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth.	ISAAC	2003	DBLP DOI BibTeX RDF
1	Amin Coja-Oghlan	Finding Large Independent Sets in Polynomial Expected Time.	STACS	2003	DBLP DOI BibTeX RDF
1	Stanislav Busygin, Sergiy Butenko, Panos M. Pardalos	A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a Sphere.	J. Comb. Optim.	2002	DBLP DOI BibTeX RDF
1	Cécile Murat, Vangelis Th. Paschos	A priori optimization for the probabilistic maximum independent set problem.	Theor. Comput. Sci.	2002	DBLP DOI BibTeX RDF
1	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
1	Jochen Alber, Jirí Fiala	Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs.	IFIP TCS	2002	DBLP BibTeX RDF
1	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
1	Alexey Glebov, Sergey Gavrilov, David Blaauw, Vladimir Zolotov	False-noise analysis using logic implications.	ACM Trans. Design Autom. Electr. Syst.	2002	DBLP DOI BibTeX RDF	circuit logic, VLSI (very large scale integration), noise analysis
1	Amin Coja-Oghlan	Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming.	MFCS	2002	DBLP DOI BibTeX RDF
1	Yvo Desmedt, Yongge Wang	Efficient Zero-Knowledge Proofs for Some Practical Graph Problems.	SCN	2002	DBLP DOI BibTeX RDF	complexity, graph theory, secret sharing, Zero-knowledge, key-escrow
1	Nissan Lev-Tov, David Peleg	Exact Algorithms and Approximation Schemes for Base Station Placement Problems.	SWAT	2002	DBLP DOI BibTeX RDF