Search results for "Polynomial algorithm"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Guillaume Damiand, Colin de la Higuera, Jean-Christophe Janodet, Émilie Samuel, Christine Solnon	A Polynomial Algorithm for Submap Isomorphism.	GbRPR	2009	DBLP DOI BibTeX RDF
2	Hamilton Emmons, Sanatan Rai	Computational Complexity Theory.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Recognition problem, Time complexity function, Nondeterministic polynomial algorithm, Computational complexity, Combinatorial optimization, Reducibility, NP-complete problem, Efficient algorithm, Complexity theory, NP-hard problem, Polynomial algorithm, Decision problem, Exponential algorithm
2	Maren Martens, S. Thomas McCormick	A Polynomial Algorithm for Weighted Abstract Flow.	IPCO	2008	DBLP DOI BibTeX RDF
2	Alexander Clark, Rémi Eyraud, Amaury Habrard	A Polynomial Algorithm for the Inference of Context Free Languages.	ICGI	2008	DBLP DOI BibTeX RDF
2	Chengbin Chu	A faster polynomial algorithm for 2-cyclic robotic scheduling.	J. Scheduling	2006	DBLP DOI BibTeX RDF	Hoist scheduling, No-wait flowshop, Complexity, Polynomial algorithm, Cyclic scheduling
2	Peter Brucker, Svetlana A. Kravchenko	Polynomial Algorithm for Parallel Machine Mean Flow Time Scheduling Problem with Release Dates.	ICCSA	2005	DBLP DOI BibTeX RDF
2	Aurélie Beynier, Abdel-Illah Mouaddib	A polynomial algorithm for decentralized Markov decision processes with temporal constraints.	AAMAS	2005	DBLP DOI BibTeX RDF	multi-agent systems, uncertainty, planning, Markov decision processes
2	Siming Huang	Inverse Problems of Some NP-Complete Problems.	AAIM	2005	DBLP DOI BibTeX RDF	pseudo-polynomial algorithm, integer programming, Inverse problem, Knapsack problem
2	Mikhail Ju. Moshkov	On Construction of the Set of Irreducible Partial Covers.	SAGA	2005	DBLP DOI BibTeX RDF	Irreducible partial cover, totally polynomial algorithm
2	ZhiWu Li, YunAn Zhi, MengChu Zhou	A polynomial algorithm to find a set of elementary siphons in a class of Petri nets.	SMC	2004	DBLP DOI BibTeX RDF
2	Stephen Lee Hansen, Sumitra Mukherjee	A Polynomial Algorithm for Optimal Univariate Microaggregation.	IEEE Trans. Knowl. Data Eng.	2003	DBLP DOI BibTeX RDF	clustering, shortest path, Statistical databases, microaggregation, information loss, microdata protection
2	Gérard Cornuéjols, Xinming Liu, Kristina Vuskovic	A Polynomial Algorithm for Recognizing Perfect Graphs.	FOCS	2003	DBLP DOI BibTeX RDF	odd hole, decomposition, recognition algorithm, perfect graph, cleaning
2	Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten	On the Existence and Determination of Satisfactory Partitions in a Graph.	ISAAC	2003	DBLP DOI BibTeX RDF	Satisfactory partition, degree constraints, complexity, graph, NP-complete, polynomial algorithm
2	Satoru Iwata, Lisa Fleischer, Satoru Fujishige	A combinatorial strongly polynomial algorithm for minimizing submodular functions.	J. ACM	2001	DBLP DOI BibTeX RDF	Discrete optimization, submodular function, strongly polynomial algorithm
2	Nathan Linial, Alex Samorodnitsky, Avi Wigderson	A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.	Combinatorica	2000	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 90C27, 15A15, 15A12, 65B99, 90C30
2	Géraud Sénizergues	A Polynomial Algorithm Testing Partial Confluence of Basic Semi-Thue Systems.	RTA	1995	DBLP DOI BibTeX RDF	two tape finite automata, confluence, semi-Thue systems
2	Sridhar Hannenhalli, Pavel A. Pevzner	Transforming Men into Mice (Polynomial Algorithm for Genomic Distance Problem).	FOCS	1995	DBLP DOI BibTeX RDF	evolution (biological), duality (mathematics), genomic distance problem, human-mouse evolution, multi chromosomal genomes, duality theorem, computable parameters, combinatorial properties, parsimonious rearrangement scenarios, comparative physical mapping data, genome rearrangement algorithm, ZOO FISH, mammalian evolution, pattern matching, sorting, polynomial time algorithm, string matching, set theory, genetics, biology computing, strings, polynomial algorithm, genomic rearrangements
2	Olivier Goldschmidt, Dorit S. Hochbaum	Polynomial Algorithm for the k-Cut Problem	FOCS	1988	DBLP DOI BibTeX RDF	k-cut problem, edge weighted graph, k nonempty components, total edge weight, partition, NP-complete, NP hard, polynomial algorithm, vertex
1	Xing-Chao Deng, Kai-Nan Xiang, Baoyindureng Wu	Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs.	Appl. Math. Lett.	2012	DBLP DOI BibTeX RDF
1	Cenk Çaliskan	A faster polynomial algorithm for the constrained maximum flow problem.	Computers & OR	2012	DBLP DOI BibTeX RDF
1	László A. Végh	Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives.	STOC	2012	DBLP DOI BibTeX RDF
1	Pavlo A. Krokhmal	On optimality of a polynomial algorithm for random linear multidimensional assignment problem.	Optimization Letters	2011	DBLP DOI BibTeX RDF
1	Ada Che, Hongjian Hu, Michelle Chabrol, Michel Gourgand	A polynomial algorithm for multi-robot 2-cyclic scheduling in a no-wait robotic cell.	Computers & OR	2011	DBLP DOI BibTeX RDF
1	Ritesh Vispute	Errors in Improved Polynomial Algorithm For 3 Sat Proposed By Narendra Chaudhari	CoRR	2011	DBLP BibTeX RDF
1	László A. Végh	Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives	CoRR	2011	DBLP BibTeX RDF
1	Tao Wang, Guojun Dai, De Xu	A polynomial algorithm for submap isomorphism of general maps.	Pattern Recognition Letters	2011	DBLP DOI BibTeX RDF
1	Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk	The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem).	SODA	2011	DBLP BibTeX RDF
1	Seyed-Abdoreza Tahaee, Amir-Hossein Jahangir	A polynomial algorithm for partitioning problems.	ACM Trans. Embedded Comput. Syst.	2010	DBLP DOI BibTeX RDF
1	David M. Kristensen, Lavanya Kannan, Michael K. Coleman, Yuri I. Wolf, Alexander Sorokin, Eugene V. Koonin, Arcady R. Mushegian	A low-polynomial algorithm for assembling clusters of orthologous groups from intergenomic symmetric best matches.	Bioinformatics	2010	DBLP DOI BibTeX RDF
1	George B. Mertzios, Derek G. Corneil	A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs	CoRR	2010	DBLP BibTeX RDF
1	Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk	The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)	CoRR	2010	DBLP BibTeX RDF
1	Julian Zinn, Rakesh M. Verma	A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems.	Appl. Algebra Eng. Commun. Comput.	2010	DBLP DOI BibTeX RDF
1	Sami Taktak, Emmanuelle Encrenaz, Jean Lou Desbarbieux	A Polynomial Algorithm to Prove Deadlock-Freeness of Wormhole Networks.	PDP	2010	DBLP DOI BibTeX RDF	routing function, Network, deadlock, dependency graph, wormhole
1	Slawek Staworko, Iovka Boneva, Benoît Groz	The view update problem for XML.	EDBT/ICDT Workshops	2010	DBLP DOI BibTeX RDF
1	Anne Benoit, Fanny Dufossé, Matthieu Gallet, Yves Robert, Bruno Gaujal	Computing the throughput of probabilistic and replicated streaming applications.	SPAA	2010	DBLP DOI BibTeX RDF	probabilistic streaming applications, scheduling, Markov chains, replication, throughput, timed Petri nets
1	S. Thomas McCormick, Satoru Fujishige	Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization.	Math. Program.	2010	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) Primary: 65K05, Secondary: 90C27, 68W40
1	Paolo Detti	A polynomial algorithm for the multiple knapsack problem with divisible item sizes.	Inf. Process. Lett.	2009	DBLP DOI BibTeX RDF
1	Aziz Moukrim, Eric Sanlaville	A polynomial algorithm for recognizing the Am-order class.	Discrete Mathematics	2009	DBLP DOI BibTeX RDF
1	Salim Achouri, Timothée Bossart, Alix Munier Kordon	A polynomial algorithm for minDSC on a subclass of series Parallel graphs.	RAIRO - Operations Research	2009	DBLP DOI BibTeX RDF
1	Alexander Zadorojniy, Guy Even, Adam Shwartz	A Strongly Polynomial Algorithm for Controlled Queues.	Math. Oper. Res.	2009	DBLP DOI BibTeX RDF
1	Vladimir Kats, Eugene Levner	A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case.	Discrete Applied Mathematics	2009	DBLP DOI BibTeX RDF
1	Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos	The Longest Path Problem Is Polynomial on Interval Graphs.	MFCS	2009	DBLP DOI BibTeX RDF	Longest path problem, complexity, dynamic programming, interval graphs, polynomial algorithm
1	Li Zhang	The three-hub center allocation problem.	ACM Southeast Regional Conference	2009	DBLP DOI BibTeX RDF	time guarantee, complexity, hubs, economies of scale
1	Haris Aziz, Mike Paterson	False name manipulations in weighted voting games: splitting, merging and annexation.	AAMAS	2009	DBLP DOI BibTeX RDF	Banzhaf index, Shapley-Shubik index, false-name manipulation, computational complexity, weighted voting games
1	Yoram Bachrach, Reshef Meir, Michael Zuckerman, Jörg Rothe, Jeffrey S. Rosenschein	The cost of stability in weighted voting games.	AAMAS	2009	DBLP DOI BibTeX RDF	core, coalition formation, weighted voting games
1	Ronghui Hou, King-Shan Lui, Hon Sun Chiu, Kwan L. Yeung, Fred Baker	Routing in multi-hop wireless mesh networks with bandwidth guarantees.	MobiHoc	2009	DBLP DOI BibTeX RDF	qos routing, distributed algorithms, wireless mesh networks
1	Mohsen Bayati, Andrea Montanari, Amin Saberi	Generating random graphs with large girth.	SODA	2009	DBLP DOI BibTeX RDF
1	S. Charles Brubaker	Robust PCA and clustering in noisy mixtures.	SODA	2009	DBLP DOI BibTeX RDF
1	Stephen Foster, Walt Potter, Jiang Wu, Bin Hu, Yu Zhang	A history sensitive cascade model in diffusion networks.	SpringSim	2009	DBLP DOI BibTeX RDF	social network, information cascade
1	Rik Eshuis	Translating Safe Petri Nets to Statecharts in a Structure-Preserving Way.	FM	2009	DBLP DOI BibTeX RDF
1	Baris Sertkaya	Towards the Complexity of Recognizing Pseudo-intents.	ICCS	2009	DBLP DOI BibTeX RDF
1	Xiaoping Chen, Jianmin Ji, Fangzhen Lin	Computing Loops with at Most One External Support Rule for Disjunctive Logic Programs.	ICLP	2009	DBLP DOI BibTeX RDF
1	Khaled M. Elbassioni, Hans Raj Tiwary	Complexity of Approximating the Vertex Centroid of a Polyhedron.	ISAAC	2009	DBLP DOI BibTeX RDF
1	Sven Schewe	From Parity and Payoff Games to Linear Programming.	MFCS	2009	DBLP DOI BibTeX RDF
1	Xiao Yin, Daming Zhu	Polynomial-Time Algorithm for Sorting by Generalized Translocations.	TAMC	2009	DBLP DOI BibTeX RDF	translocation, Algorithm, genome rearrangement
1	Yoram Bachrach, Jeffrey S. Rosenschein	Power in threshold network flow games.	Autonomous Agents and Multi-Agent Systems	2009	DBLP DOI BibTeX RDF	Power index, Network flow, Network reliability, Coalitional games
1	Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Cécile Murat, Vangelis Th. Paschos	Probabilistic graph-coloring in bipartite and split graphs.	J. Comb. Optim.	2009	DBLP DOI BibTeX RDF	Probabilistic optimization, Approximation algorithms, Graph coloring
1	Hui Liu, Zili Shao, Meng Wang, Junzhao Du, Chun Jason Xue, Zhiping Jia	Combining Coarse-Grained Software Pipelining with DVS for Scheduling Real-Time Periodic Dependent Tasks on Multi-Core Embedded Systems.	Signal Processing Systems	2009	DBLP DOI BibTeX RDF	Periodic dependent tasks, Scheduling, Multimedia, Real-time, Dynamic voltage scaling (DVS), Multi-core, Software pipelining, Retiming
1	Ulrich Brenner	A faster polynomial algorithm for the unbalanced Hitchcock transportation problem.	Oper. Res. Lett.	2008	DBLP DOI BibTeX RDF
1	Guohui Yao, Daming Zhu, Hengwu Li, Shaohan Ma	A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem.	Discrete Mathematics	2008	DBLP DOI BibTeX RDF
1	Jarek Duda	Polynomial algorithm for graph isomorphism problem	CoRR	2008	DBLP BibTeX RDF
1	Vadim V. Lozin, Martin Milanic	A polynomial algorithm to find an independent set of maximum weight in a fork-free graph.	J. Discrete Algorithms	2008	DBLP DOI BibTeX RDF
1	Sergio Pozo Hidalgo, Rafael Ceballos, Rafael Martinez Gasca	A Heuristic Polynomial Algorithm for Local Inconsistency Diagnosis in Firewall Rule Sets.	SECRYPT	2008	DBLP BibTeX RDF
1	Cun-Quan Zhang, Yongbin Ou	Clustering, community partition and disjoint spanning trees.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	dynamic density, clustering, community, hierarchical clustering, Spanning trees, polynomial algorithm, dense subgraph
1	Alain Hertz, Sacha Varone	The Metric Cutpoint Partition Problem.	J. Classification	2008	DBLP DOI BibTeX RDF	Optimal realizations, Cutpoint, Metric spaces, Bridge, Polynomial algorithm
1	Dan Trietsch, Kenneth R. Baker	Minimizing the number of tardy jobs with stochastically-ordered processing times.	J. Scheduling	2008	DBLP DOI BibTeX RDF	Sequencing, Polynomial algorithm, Stochastic scheduling
1	S. Thomas McCormick, Satoru Fujishige	Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization.	SODA	2008	DBLP DOI BibTeX RDF
1	Bennett Thompson, David J. Pearce, Craig Anslow, Gary Haggard	Visualizing the computation tree of the Tutte Polynomial.	SOFTVIS	2008	DBLP DOI BibTeX RDF	software visualization, Tutte Polynomial
1	Uwe Naumann, Yuxiao Hu	Optimal vertex elimination in single-expression-use graphs.	ACM Trans. Math. Softw.	2008	DBLP DOI BibTeX RDF	Vertex elimination, single-expression-use graph
1	Maolin Tang, Yanming Feng	Area-Oriented Reference Station Placement for Network RTK.	CSSE	2008	DBLP DOI BibTeX RDF
1	Congying Han, Guoping He, Hua Duan, Xuping Zhang	A Binding Number Computation of Graph.	FSKD	2008	DBLP DOI BibTeX RDF
1	Thierry Vallée, Alain Bretto	Hamiltonicity of Simplicial-Connected Graphs: An Algorithm Based on Clique Decomposition.	ITNG	2008	DBLP DOI BibTeX RDF	Clique Covering, Network, Graph Theory, Graph Algorithms, Hamiltonicity
1	Josée Desharnais, François Laviolette, Mathieu Tracol	Approximate Analysis of Probabilistic Processes: Logic, Simulation and Games.	QEST	2008	DBLP DOI BibTeX RDF
1	Alfredo Benso, Alberto Bosio, Stefano Di Carlo, Giorgio Di Natale, Paolo Prinetto	March Test Generation Revealed.	IEEE Trans. Computers	2008	DBLP DOI BibTeX RDF
1	Fernando Solano, Ramón Fabregat, José-Luis Marzo	On optimal computation of MPLS label binding for multipoint-to-point connections.	IEEE Transactions on Communications	2008	DBLP DOI BibTeX RDF
1	Leo Liberti, Franco Raimondi	The Secret Santa Problem.	AAIM	2008	DBLP DOI BibTeX RDF
1	Benoît Darties, Sylvain Durand, Jérôme Palaysi	Request Satisfaction Problem in Synchronous Radio Networks.	ADHOC-NOW	2008	DBLP DOI BibTeX RDF	Request Satisfaction, Complexity, Radio Network
1	Mathias Möhl, Sebastian Will, Rolf Backofen	Fixed Parameter Tractable Alignment of RNA Structures Including Arbitrary Pseudoknots.	CPM	2008	DBLP DOI BibTeX RDF	RNA alignment, fixed parameter tractability, pseudoknots
1	Yury Savateev	Lambek Grammars with One Division Are Decidable in Polynomial Time.	CSR	2008	DBLP DOI BibTeX RDF
1	Maxim A. Babenko, Alexander V. Karzanov	A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem.	ESA	2008	DBLP DOI BibTeX RDF
1	Markus Chimani, Petr Hlinený, Petra Mutzel	Approximating the Crossing Number of Apex Graphs.	Graph Drawing	2008	DBLP DOI BibTeX RDF	apex graph, vertex insertion, Crossing number
1	Antonio Cano Gómez, Gloria Inés Alvarez	Learning Commutative Regular Languages.	ICGI	2008	DBLP DOI BibTeX RDF
1	Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani	New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem.	IPCO	2008	DBLP DOI BibTeX RDF
1	Kenjiro Takazawa	A Weighted Kt, t-Free t-Factor Algorithm for Bipartite Graphs.	IPCO	2008	DBLP DOI BibTeX RDF
1	Yoan Renaud	Join on Closure Systems Using Direct Implicational Basis Representation.	MCO	2008	DBLP DOI BibTeX RDF	closure systems, implicational basis, direct basis, datamining
1	Hajo Broersma, Daniël Paulusma	Computing Sharp 2-Factors in Claw-Free Graphs.	MFCS	2008	DBLP DOI BibTeX RDF
1	Mikhail Moshkov, Andrzej Skowron, Zbigniew Suraj	On Irreducible Descriptive Sets of Attributes for Information Systems.	RSCTC	2008	DBLP DOI BibTeX RDF	maximal consistent extensions, irreducible descriptive sets, rough sets, information systems
1	Tomás Kroupa	Geometry of Cores of Submodular Coherent Upper Probabilities and Possibility Measures.	SMPS	2008	DBLP DOI BibTeX RDF	Coherent upper probability, Core, Possibility measure
1	Xiaowen Lou, Daming Zhu	Genome Rearrangement Algorithms for Unsigned Permutations with O(logn) Singletons.	TAMC	2008	DBLP DOI BibTeX RDF
1	Elisabeth Gassner, Johannes Hatzl, Sven Oliver Krumke, Heike Sperber, Gerhard J. Woeginger	How Hard Is It to Find Extreme Nash Equilibria in Network Congestion Games?	WINE	2008	DBLP DOI BibTeX RDF	Network congestion game, makespan objective, extreme equilibria, complexity, unsplittable flow
1	Rodrigo de A. Hausen, Luerbio Faria, Celina M. Herrera de Figueiredo, Luis Antonio Brasil Kowada	On the Toric Graph as a Tool to Handle the Problem of Sorting by Transpositions.	BSB	2008	DBLP DOI BibTeX RDF
1	Pierre Charbit, András Sebö	Cyclic orders: Equivalence and duality.	Combinatorica	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 05C38, 90C27, 90C10, 05C70, 05C20
1	Friedrich Eisenbrand, Gianpaolo Oriolo, Gautier Stauffer, Paolo Ventura	The stable set polytope of quasi-line graphs.	Combinatorica	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90C57, 90C10
1	Olivier Marchetti, Alix Munier Kordon	Minimizing Place Capacities of Weighted Event Graphs for Enforcing Liveness.	Discrete Event Dynamic Systems	2008	DBLP DOI BibTeX RDF	Petri nets, Manufacturing, Liveness, Buffer requirement
1	Jerzy W. Grzymala-Busse, Wojciech Rzasa	Local and Global Approximations for Incomplete Data.	T. Rough Sets	2008	DBLP DOI BibTeX RDF
1	M. Z. Arslanov	A polynomial algorithm for one problem of guillotine cutting.	Oper. Res. Lett.	2007	DBLP DOI BibTeX RDF
1	Kiyohito Nagano	A strongly polynomial algorithm for line search in submodular polyhedra.	Discrete Optimization	2007	DBLP DOI BibTeX RDF
1	Lukasz Kuszner, Michal Malafiejski	A polynomial algorithm for some preemptive multiprocessor task scheduling problems.	European Journal of Operational Research	2007	DBLP DOI BibTeX RDF
1	Marcos Colebrook, Joaquin Sicilia	A polynomial algorithm for the multicriteria cent-dian location problem.	European Journal of Operational Research	2007	DBLP DOI BibTeX RDF
1	Jose Gutiérrez, Antonio Sedeño-Noda, Marcos Colebrook, Joaquin Sicilia	A polynomial algorithm for the production/ordering planning problem with limited storage.	Computers & OR	2007	DBLP DOI BibTeX RDF