Search results for "Subgraph Problem"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Timo Poranen	Heuristics for the Maximum Outerplanar Subgraph Problem.	J. Heuristics	2005	DBLP DOI BibTeX RDF	triangular cactus heuristic, maximum outerplanar subgraph problem, simulated annealing
2	Jack Brimberg, Nenad Mladenovic, Dragan Urosevic	Local and variable neighborhood search for the k -cardinality subgraph problem.	J. Heuristics	2008	DBLP DOI BibTeX RDF	k-subgraph, Variable neighborhood search
2	Philip Brisk, Majid Sarrafzadeh	Interference graphs for procedures in static single information form are interval graphs.	SCOPES	2007	DBLP DOI BibTeX RDF	k-colorable subgraph problem, linear scan register allocation, static single information (SSI) form, compilers, register allocation, interval graph
2	Mohammad Taghi Hajiaghayi, Kamal Jain, Lap Chi Lau, Ion I. Mandoiu, Alexander Russell, Vijay V. Vazirani	Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping.	International Conference on Computational Science	2006	DBLP DOI BibTeX RDF
2	Dan Zhang, Zeng-zhi Li, Hong Song, Tao Zhan	Particle Swarm Optimization for Bipartite Subgraph Problem: A Case Study.	ICNC	2005	DBLP DOI BibTeX RDF
2	Prabhakar Gubbala, Balaji Raghavachari	Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem.	IPCO	2005	DBLP DOI BibTeX RDF
2	Per Olov Lindberg, Gholamreza Razmara	The Prize Collecting Connected Subgraph Problem - A New NP-Hard Problem arising in Snow Removal Routing.	OR	2004	DBLP DOI BibTeX RDF
2	Elder M. Macambira	An Application of Tabu Search Heuristic for the Maximum Edge-Weighted Subgraph Problem.	Annals OR	2002	DBLP DOI BibTeX RDF	edge-weighted subgraph problem, combinatorial optimization, tabu search, metaheuristics
2	Robert Carr, R. Ravi	A New Bound for the 2-Edge Connected Subgraph Problem.	IPCO	1998	DBLP DOI BibTeX RDF
2	Anand Srivastav, Katja Wolf	Finding Dense Subgraphs with Semidefinite Programming.	APPROX	1998	DBLP DOI BibTeX RDF	Subgraph Problem, Approximation Algorithms, Randomized Algorithms, Semidefinite Programming
2	Alexander E. Andreev, Andrea E. F. Clementi, Pierluigi Crescenzi, Elias Dahlhaus, Sergio De Agostino, José D. P. Rolim	The Parallel Complexity of Approximating the High Degree Subgraph Problem.	ISAAC	1995	DBLP DOI BibTeX RDF
2	Viggo Kann	On the Approximability of the Maximum Common Subgraph Problem.	STACS	1992	DBLP DOI BibTeX RDF	computational complexity, Approximation, graph problems
1	Mathieu Lacroix, Ali Ridha Mahjoub, Sébastien Martin, Christophe Picouleau	On the NP-completeness of the perfect matching free subgraph problem.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
1	Justo Puerto, Arie Tamir, Federico Perea	Cooperative location games based on the minimum diameter spanning Steiner subgraph problem.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos	Reoptimization of the Maximum Weighted P k -Free Subgraph Problem under Vertex Insertion.	WALCOM	2012	DBLP DOI BibTeX RDF
1	Emilio Di Giacomo, Walter Didimo, Luca Grilli, Giuseppe Liotta, Salvatore Agostino Romeo	Heuristics for the Maximum 2-layer RAC Subgraph Problem.	WALCOM	2012	DBLP DOI BibTeX RDF
1	Tim Januschowski, Marc E. Pfetsch	The maximum k-colorable subgraph problem and orbitopes.	Discrete Optimization	2011	DBLP DOI BibTeX RDF
1	Ján Katrenic, Ingo Schiermeyer	Improved approximation bounds for the minimum rainbow subgraph problem.	Inf. Process. Lett.	2011	DBLP DOI BibTeX RDF
1	Bundit Laekhanukit	An improved approximation algorithm for the minimum-cost subset k-connected subgraph problem	CoRR	2011	DBLP BibTeX RDF
1	Fedor V. Fomin, Ioan Todinca, Yngve Villanger	Exact Algorithm for the Maximum Induced Planar Subgraph Problem.	ESA	2011	DBLP DOI BibTeX RDF
1	Cui Zhang, Li-Qing Zhao, Rong Long Wang	A Saturation Binary Neural Network for Bipartite Subgraph Problem.	ICIC	2011	DBLP DOI BibTeX RDF
1	Emanuele Rodaro, Pedro V. Silva	Never Minimal Automata and the Rainbow Bipartite Subgraph Problem.	Developments in Language Theory	2011	DBLP DOI BibTeX RDF
1	Tim Januschowski, Marc E. Pfetsch	Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry.	CPAIOR	2011	DBLP DOI BibTeX RDF
1	Jonathan Backer, J. Mark Keil	Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs.	Inf. Process. Lett.	2010	DBLP DOI BibTeX RDF
1	Stephan Matos Camacho, Ingo Schiermeyer, Zsolt Tuza	Approximation algorithms for the minimum rainbow subgraph problem.	Discrete Mathematics	2010	DBLP DOI BibTeX RDF
1	Fatiha Bendali, I. Diarrassouba, Ali Ridha Mahjoub, Mohamed Didi Biha, Jean Mailfert	A branch-and-cut algorithm for the k-edge connected subgraph problem.	Networks	2010	DBLP DOI BibTeX RDF
1	Firdovsi Sharifov	Perfectly matchable subgraph problem on a bipartite graph.	RAIRO - Operations Research	2010	DBLP DOI BibTeX RDF
1	Milena Bogdanovic	An ILP formulation and genetic algorithm for the Maximum Degree-Bounded Connected Subgraph problem.	Computers & Mathematics with Applications	2010	DBLP DOI BibTeX RDF
1	Gordana Manic, Laura Bahiense, Cid C. de Souza	A branch&cut algorithm for the maximum common edge subgraph problem.	Electronic Notes in Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Flavia Bonomo, Javier Marenco, Daniela Sabán, Nicolás Stier Moses	A polyhedral study of the maximum edge subgraph problem.	Electronic Notes in Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Romeo Rizzi	Approximating the maximum 3-edge-colorable subgraph problem.	Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Doron Goldstein, Michael Langberg	The Dense k Subgraph problem	CoRR	2009	DBLP BibTeX RDF
1	Andrea Bettinelli, Leo Liberti, Franco Raimondi, David Savourey	The Anonymous Subgraph Problem.	CTW	2009	DBLP BibTeX RDF
1	Viswanath Nagarajan, Maxim Sviridenko	On the maximum quadratic assignment problem.	SODA	2009	DBLP DOI BibTeX RDF
1	Zeev Nutov	An almost O(log k)-approximation for k-connected subgraphs.	SODA	2009	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Ali Kemal Sinop	Improved Inapproximability Results for Maximum k-Colorable Subgraph.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Tommy Färnqvist, Peter Jonsson, Johan Thapper	Approximability Distance in the Space of H-Colourability Problems.	CSR	2009	DBLP DOI BibTeX RDF	graph H-colouring, computational complexity, approximability, optimisation, graph homomorphism
1	Samir Khuller, Barna Saha	On Finding Dense Subgraphs.	ICALP	2009	DBLP DOI BibTeX RDF
1	Sebastian Böcker, Falk Hüffner, Anke Truß, Magnus Wahlström	A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams.	IWPEC	2009	DBLP DOI BibTeX RDF
1	Reid Andersen, Kumar Chellapilla	Finding Dense Subgraphs with Size Bounds.	WAW	2009	DBLP DOI BibTeX RDF
1	Timo Poranen	Two New Approximation Algorithms for the Maximum Planar Subgraph Problem.	Acta Cybern.	2008	DBLP BibTeX RDF
1	Sriraman Sridharan	Polynomial time algorithms for two classes of subgraph problem.	RAIRO - Operations Research	2008	DBLP DOI BibTeX RDF
1	Omid Amini, Ignasi Sau, Saket Saurabh	Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem.	IWPEC	2008	DBLP DOI BibTeX RDF
1	Jittat Fakcharoenphol, Bundit Laekhanukit	An o(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem.	STOC	2008	DBLP DOI BibTeX RDF	approximation algorithms for NP-hard problems, k-connected spanning subgraphs, network design
1	Akiko Suzuki, Takeshi Tokuyama	Dense subgraph problems with output-density conditions.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	approximation algorithms, Combinatorial optimization, randomized algorithms, dense subgraph
1	Vinayaka Pandit, Natwar Modani, Sougata Mukherjea, Amit Anil Nanavati, Sambuddha Roy, Amit Agarwal	Extracting dense communities from telecom call graphs.	COMSWARE	2008	DBLP DOI BibTeX RDF
1	Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung	Degree Bounded Network Design with Metric Costs.	FOCS	2008	DBLP DOI BibTeX RDF
1	Yalan Zhou, Jiahai Wang, Jian Yin	Genetic Particle Swarm Optimization Based on Multiagent Model for Combinatorial Optimization Problem.	ICNSC	2008	DBLP DOI BibTeX RDF
1	Toshinori Yamada	Minimum energy broadcasting in wireless networks (extended abstract).	ISCAS	2008	DBLP DOI BibTeX RDF
1	Elmahdi Driouch, Wessam Ajib	A graph theory based scheduling algorithm For MIMO-CDMA systems using zero forcing beamforming.	ISCC	2008	DBLP DOI BibTeX RDF
1	Guy Kortsarz, Michael Langberg, Zeev Nutov	Approximating Maximum Subgraphs without Short Cycles.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	MohammadAli Safari, Mohammad R. Salavatipour	A Constant Factor Approximation for Minimum lambda-Edge-Connected k-Subgraph with Metric Costs.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Carla P. Gomes, Willem Jan van Hoeve, Ashish Sabharwal	Connections in Networks: A Hybrid Approach.	CPAIOR	2008	DBLP DOI BibTeX RDF
1	Markus Chimani, Carsten Gutwenger, Mathias Jansen, Karsten Klein, Petra Mutzel	Computing Maximum C-Planar Subgraphs.	Graph Drawing	2008	DBLP DOI BibTeX RDF
1	Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko	Approximating Minimum-Power Degree and Connectivity Problems.	LATIN	2008	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh	Iterative Compression and Exact Algorithms.	MFCS	2008	DBLP DOI BibTeX RDF
1	Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, Saket Saurabh	Degree-Constrained Subgraph Problems: Hardness and Approximation Results.	WAOA	2008	DBLP DOI BibTeX RDF	Degree-Constrained Subgraphs, Apx, Excluded Minor, Approximation Algorithms, Hardness of Approximation, PTAS
1	Maria Liazi, Ioannis Milis, Fanny Pascual, Vassilis Zissimopoulos	The densest k-subgraph problem on clique graphs.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Densest k-subgraph, Clique graph, Dynamic programming, Polynomial time approximation scheme
1	Venkatesh Raman, Somnath Sikdar	Parameterized complexity of the induced subgraph problem in directed graphs.	Inf. Process. Lett.	2007	DBLP DOI BibTeX RDF
1	Harish Sethu	The Induced Bounded-Degree Subgraph Problem and Stream Control in MIMO Networks	CoRR	2007	DBLP BibTeX RDF
1	Denis Cornaz, Ali Ridha Mahjoub	The Maximum Induced Bipartite Subgraph Problem with Edge Weights.	SIAM J. Discrete Math.	2007	DBLP DOI BibTeX RDF
1	Petteri Hintsanen	The Most Reliable Subgraph Problem.	PKDD	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	Wenyuan Li, Ying Liu, Hung-Chung Huang, Yanxiong Peng, Yongjing Lin, Wee Keong Ng, Kok-Leong Ong	Dynamical Systems for Discovering Protein Complexes and Functional Modules from Biological Networks.	IEEE/ACM Trans. Comput. Biology Bioinform.	2007	DBLP DOI BibTeX RDF	bioinformatics databases, evolutionary computing, Graph algorithms, neural nets
1	Moses Charikar, Konstantin Makarychev, Yury Makarychev	On the Advantage over Random for Maximum Acyclic Subgraph.	FOCS	2007	DBLP DOI BibTeX RDF
1	Peng Zhang	Approximating Generalized Multicut on Trees.	CiE	2007	DBLP DOI BibTeX RDF	Generalized Multicut, Approximation Algorithm, Combinatorial Optimization, Tree
1	Jon Conrad, Carla P. Gomes, Willem Jan van Hoeve, Ashish Sabharwal, Jordan Suter	Connections in Networks: Hardness of Feasibility Versus Optimality.	CPAIOR	2007	DBLP DOI BibTeX RDF
1	Jiahai Wang	A Hybrid of Particle Swarm Optimization and Hopfield Networks for Bipartite Subgraph Problems.	ISNN	2007	DBLP DOI BibTeX RDF
1	Prabhakar Gubbala, Balaji Raghavachari	A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity.	WADS	2007	DBLP DOI BibTeX RDF	Approximation algorithms, Combinatorial Optimization, Connectivity, Graph and network algorithms
1	Falk Hüffner, Nadja Betzler, Rolf Niedermeier	Optimal Edge Deletions for Signed Graph Balancing.	WEA	2007	DBLP DOI BibTeX RDF
1	Adrian Kosowski, Michal Malafiejski, Pawel Zylinski	Packing [1, Delta] -factors in graphs of small degree.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Packing factors, Edge-colorable subgraph, Fault tolerant guards
1	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov	Power optimization for connectivity problems.	Math. Program.	2007	DBLP DOI BibTeX RDF
1	Mourad Baïou, José R. Correa	The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation.	Discrete Optimization	2006	DBLP DOI BibTeX RDF
1	Rong Long Wang, Kozo Okazaki	A Hill-Shift Learning Algorithm of Hopfield Network for Bipartite Subgraph Problem.	IEICE Transactions	2006	DBLP DOI BibTeX RDF
1	Pierre Fouilhoux, Ali Ridha Mahjoub	Polyhedral results for the bipartite induced subgraph problem.	Discrete Applied Mathematics	2006	DBLP DOI BibTeX RDF
1	Denis Cornaz	A linear programming formulation for the maximum complete multipartite subgraph problem.	Math. Program.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (1991) 05C15, 90C09
1	Mohammad Taghi Hajiaghayi, Kamal Jain	The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema.	SODA	2006	DBLP DOI BibTeX RDF
1	Xiuzhen Huang, Jing Lai	Maximum Common Subgraph: Upper Bound and Lower Bound Results.	IMSCCS	2006	DBLP DOI BibTeX RDF
1	Danny Segev, Gil Segev	Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing.	ESA	2006	DBLP DOI BibTeX RDF
1	Virginia Vassilevska, Ryan Williams, Raphael Yuster	Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems.	ICALP	2006	DBLP DOI BibTeX RDF
1	Mourad Baïou, José R. Correa	The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation.	Electronic Notes in Discrete Mathematics	2005	DBLP DOI BibTeX RDF
1	W. Henry Suters, Faisal N. Abu-Khzam, Yun Zhang, Christopher T. Symons, Nagiza F. Samatova, Michael A. Langston	A New Approach and Faster Exact Methods for the Maximum Common Subgraph Problem.	COCOON	2005	DBLP DOI BibTeX RDF
1	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov	Power Optimization for Connectivity Problems.	IPCO	2005	DBLP DOI BibTeX RDF
1	Akiko Suzuki, Takeshi Tokuyama	Dense Subgraph Problems with Output-Density Conditions.	ISAAC	2005	DBLP DOI BibTeX RDF
1	Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse	Local approximations for maximum partial subgraph problem.	Oper. Res. Lett.	2004	DBLP DOI BibTeX RDF
1	Jiahai Wang, Zheng Tang, Rong Long Wang	An Annealed Chaotic Maximum Neural Network For Bipartite Subgraph Problem.	Int. J. Neural Syst.	2004	DBLP DOI BibTeX RDF
1	Rong Long Wang, Zheng Tang, Qi Ping Cao	A Hopfield network learning method for bipartite subgraph problem.	IEEE Transactions on Neural Networks	2004	DBLP DOI BibTeX RDF
1	Timo Poranen	A simulated annealing algorithm for the maximum planar subgraph problem.	Int. J. Comput. Math.	2004	DBLP DOI BibTeX RDF
1	Magnús M. Halldórsson, Joseph Y. Halpern, Erran L. Li, Vahab S. Mirrokni	On spectrum sharing games.	PODC	2004	DBLP DOI BibTeX RDF	approximation algorithm, game theory, Nash equilibrium, graph coloring, price of anarchy, unit disk graph
1	Yanxia Rong, Hongsik Choi, Hyeong-Ah Choi	Dual Power Management for Network Connectivity in Wireless Sensor Networks.	IPDPS	2004	DBLP DOI BibTeX RDF
1	A. Volgenant, C. W. Duin	On Steiner Versions of (bi)Connectivity in Network Problems.	Graphs and Combinatorics	2004	DBLP DOI BibTeX RDF	Bottleneck optimization, Steiner (bi)connectivity, Steiner bipartition, Algorithms, Combinatorial problems
1	Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos	A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem.	Inf. Process. Lett.	2003	DBLP DOI BibTeX RDF
1	Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki	A linear time 5/3-approximation for the minimum strongly-connected spanning subgraph problem.	Inf. Process. Lett.	2003	DBLP DOI BibTeX RDF
1	Donatello Conte, C. Guidobaldi, Carlo Sansone	A Comparison of Three Maximum Common Subgraph Algorithms on a Large Database of Labeled Graphs.	GbRPR	2003	DBLP DOI BibTeX RDF
1	Atsuko Yamaguchi, Hiroshi Mamitsuka	Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of Spanning Trees.	ISAAC	2003	DBLP DOI BibTeX RDF
1	Gruia Calinescu, Cristina G. Fernandes, Howard J. Karloff, Alexander Zelikovsky	A New Approximation Algorithm for Finding Heavy Planar Subgraphs.	Algorithmica	2003	DBLP DOI BibTeX RDF	Weighted planar graph, Approximation algorithm, Performance ratio
1	Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai	Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs.	Algorithmica	2003	DBLP DOI BibTeX RDF	Sum Coloring, Scheduling dependent jobs, Approximation algorithms, Multicoloring
1	Guy Kortsarz, Zeev Nutov	Approximating Node Connectivity Problems via Set Covers.	Algorithmica	2003	DBLP DOI BibTeX RDF	Vertex connected spanning subgraph, Metric costs, Approximation algorithms
1	Guy Kortsarz, Robert Krauthgamer, James R. Lee	Hardness of Approximation for Vertex-Connectivity Network-Design Problems.	APPROX	2002	DBLP DOI BibTeX RDF
1	Sabine Bachl, Franz-Josef Brandenburg	Computing and Drawing Isomorphic Subgraphs.	Graph Drawing	2002	DBLP DOI BibTeX RDF