Search results for "polynomial-time algorithms"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Grzegorz W. Wasilkowski, Henryk Wozniakowski	Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights: Average Case Setting.	Foundations of Computational Mathematics	2009	DBLP DOI BibTeX RDF	Multivariate linear problems, Finite-order weights, Small effective dimension, Average case setting, Polynomial-time algorithms, Tractability
3	Grzegorz W. Wasilkowski, Henryk Wozniakowski	Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights: Worst Case Setting.	Foundations of Computational Mathematics	2005	DBLP DOI BibTeX RDF	Multivariate linear problems, Finiteorder weights, Small effective dimension, Polynomial-time algorithms, Tractability
2	Evmorfia N. Argyriou, Michael A. Bekos, Michael Kaufmann, Antonios Symvonis	Two Polynomial Time Algorithms for the Metro-line Crossing Minimization Problem.	Graph Drawing	2008	DBLP DOI BibTeX RDF
2	Anders Dessmark, Jesper Jansson, Andrzej Lingas, Eva-Marta Lundell	Polynomial-Time Algorithms for the Ordered Maximum Agreement Subtree Problem.	Algorithmica	2007	DBLP DOI BibTeX RDF
2	Xiaoguang Yang, Jianzhong Zhang 0001	Some inverse min-max network problems under weighted l1 and linfinity norms with bound constraints on changes.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Inverse min-max network problem, Weighted l 1 norm, Weighted l? norm, Bound constraints, Polynomial time algorithms
2	Sidharth Jaggi, Peter Sanders, Philip A. Chou, Michelle Effros, Sebastian Egner, Kamal Jain, Ludo M. G. M. Tolhuizen	Polynomial time algorithms for multicast network code construction.	IEEE Transactions on Information Theory	2005	DBLP DOI BibTeX RDF
2	Bruno Codenotti, Benton McCune, Kasturi R. Varadarajan	Market equilibrium via the excess demand function.	STOC	2005	DBLP DOI BibTeX RDF	tâtonnement, algorithms, approximation, polynomial-time algorithms, market equilibrium
2	Anders Dessmark, Jesper Jansson, Andrzej Lingas, Eva-Marta Lundell	Polynomial-Time Algorithms for the Ordered Maximum Agreement Subtree Problem.	CPM	2004	DBLP DOI BibTeX RDF
2	Peter Sanders, Sebastian Egner, Ludo M. G. M. Tolhuizen	Polynomial time algorithms for network information flow.	SPAA	2003	DBLP DOI BibTeX RDF	communication, multicasting, randomized algorithm, finite field, coding, linear algebra, derandomization, network information theory
2	Johanne Cohen, Pierre Fraigniaud, Margarida Mitjana	Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees.	Theory Comput. Syst.	2002	DBLP DOI BibTeX RDF
2	Peter A. Beling	Exact Algorithms for Linear Programming over Algebraic Extensions.	Algorithmica	2001	DBLP DOI BibTeX RDF	Ellipsoid method, Computational complexity, Linear programming, Polynomial-time algorithms, Symbolic computation, Algebraic numbers
2	Bruce M. Maggs, Berthold Vöcking	Improved Routing and Sorting on Multibutterflies.	Algorithmica	2000	DBLP DOI BibTeX RDF	Ellipsoid method, Computational complexity, Linear programming, Polynomial-time algorithms, Symbolic computation, Algebraic numbers
2	Deng-Jyi Chen, Ming-Sang Chang, C. I. Yang, Kuo-Lung Ku	Multimedia task reliability analysis based on token ring network. (PDF / PS)	ICPADS	1996	DBLP DOI BibTeX RDF	multimedia task reliability analysis, reliability analyses, multimedia task reliability, time-constraint multimedia task reliability, multimedia systems, polynomial-time algorithms, reliability models, distributed multimedia system, token networks, token ring network
2	Theodora A. Varvarigou, Vwani P. Roychowdhury, Thomas Kailath, Eugene L. Lawler	Scheduling In and Out Forests in the Presence of Communication Delays.	IEEE Trans. Parallel Distrib. Syst.	1996	DBLP DOI BibTeX RDF	out-forest precedence graphs, out-forest precedence graphs, optimal deterministic schedules, polynomial-time algorithms, Communication delays, multiprocessor architectures
2	Qi Ning, Vincent Van Dongen, Guang R. Gao	Automatic data and computation decomposition for distributed memory machines.	HICSS	1995	DBLP DOI BibTeX RDF	automatic data decomposition, automatic computation decomposition, compile-time technique, complex programs, perfect loop nests, nonperfect loop nests, loop-carried dependences, loop nest clusters, data locality constraint relaxation, homogeneous linear equations, hierarchical program nesting structures, nesting levels, compiler development, EPPP project, Environment for Portable Parallel Programming, computational complexity, parallel programming, parallelism, polynomial time algorithms, distributed memory systems, software portability, relaxation, distributed memory machines, program control structures, parallelising compilers, data redistributions, equations, data handling
2	Alexander Tuzikov, Mikhail Makhaniok, Reinhard Männer	Bicriterion scheduling of identical processing time jobs by uniform processors. (PDF / PS)	IPPS	1995	DBLP DOI BibTeX RDF	bicriterion scheduling, identical processing time jobs, uniform processors, multicriterion job scheduling, parallel algorithms, computational complexity, polynomial time algorithms, processor scheduling, operations research
2	Rajat K. Pal, Sudebkumar Prasant Pal, M. M. Das, Ajit Pal	Computing area and wire length efficient routes for channels.	VLSI Design	1995	DBLP DOI BibTeX RDF	area efficient routes, wire length efficient routes, total wire length reduction, multilayer routing solutions, computational complexity, VLSI, NP-hard, polynomial time algorithms, network routing, circuit layout CAD, minimisation, VLSI layout, integrated circuit layout, channel routing
2	Ravi Kannan	Markov Chains and Polynomial Time Algorithms	FOCS	1994	DBLP DOI BibTeX RDF	approximately certain, Markov Chains, randomized algorithms, polynomial time algorithms, perfect matchings, counting problems
1	Ming-Yang Kao, Henry C. M. Leung, He Sun, Yong Zhang	Deterministic Polynomial-Time Algorithms for Designing Short DNA Words	CoRR	2012	DBLP BibTeX RDF
1	Kousha Etessami, Alistair Stewart, Mihalis Yannakakis	Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars	CoRR	2012	DBLP BibTeX RDF
1	Kousha Etessami, Alistair Stewart, Mihalis Yannakakis	Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations	CoRR	2012	DBLP BibTeX RDF
1	Michael Geilke, Sandra Zilles	Polynomial-Time Algorithms for Learning Typed Pattern Languages.	LATA	2012	DBLP DOI BibTeX RDF
1	Kousha Etessami, Alistair Stewart, Mihalis Yannakakis	Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars.	STOC	2012	DBLP DOI BibTeX RDF
1	Gregor L. Pardella	Efficient Polynomial-Time Algorithms for Special Graph Partitioning Problems.		2011	RDF
1	Jugal Garg, Albert Xin Jiang, Ruta Mehta	Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses	CoRR	2011	DBLP BibTeX RDF
1	Jugal Garg, Albert Xin Jiang, Ruta Mehta	Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses.	WINE	2011	DBLP DOI BibTeX RDF
1	Bin Fu, Haitao Jiang, Boting Yang, Binhai Zhu	Exponential and Polynomial Time Algorithms for the Minimum Common String Partition Problem.	COCOA	2011	DBLP DOI BibTeX RDF
1	Gilles Simonin, Rodolphe Giroudeau, Jean-Claude König	Polynomial-time algorithms for scheduling problem for coupled-tasks in presence of treatment tasks.	Electronic Notes in Discrete Mathematics	2010	DBLP DOI BibTeX RDF
1	Dorit S. Hochbaum	Polynomial Time Algorithms for Ratio Regions and a Variant of Normalized Cut.	IEEE Trans. Pattern Anal. Mach. Intell.	2010	DBLP DOI BibTeX RDF	image segmentation, partitioning, Grouping, graph theoretic methods
1	Marie E. Matta, Salah E. Elmaghraby	Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop.	European Journal of Operational Research	2010	DBLP DOI BibTeX RDF
1	Rafael P. Laufer, Henri Dubois-Ferrière, Leonard Kleinrock	Polynomial-Time Algorithms for Multirate Anypath Routing in Wireless Multihop Networks	CoRR	2010	DBLP BibTeX RDF
1	Gábor Ivanyos, Marek Karpinski, Nitin Saxena	Deterministic Polynomial Time Algorithms for Matrix Completion Problems.	SIAM J. Comput.	2010	DBLP DOI BibTeX RDF
1	Ming-Yang Kao, Henry C. M. Leung, He Sun, Yong Zhang	Deterministic Polynomial-Time Algorithms for Designing Short DNA Words.	TAMC	2010	DBLP DOI BibTeX RDF
1	Felix Brandt, Markus Brill, Edith Hemaspaandra, Lane A. Hemaspaandra	Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates.	AAAI	2010	DBLP BibTeX RDF
1	Hiroshi Hirai	The maximum multiflow problems with bounded fractionality.	STOC	2010	DBLP DOI BibTeX RDF	metrics, polynomial time algorithms, multicommodity flows
1	Lei Zhang 0004, Alexander Brodsky, Sushil Jajodia	Restoring compromised privacy in micro-data disclosure.	ASIACCS	2010	DBLP DOI BibTeX RDF	micro-data disclosure, data privacy
1	Maciej Liskiewicz, Johannes Textor	Negative selection algorithms without generating detectors.	GECCO	2010	DBLP DOI BibTeX RDF	consistent learning, artificial immune systems, negative selection
1	Amotz Bar-Noy, Panagiotis Cheilaris, Yi Feng 0002, Asaf Levin	Finding mobile data under delay constraints with searching costs.	PODC	2010	DBLP DOI BibTeX RDF	partitioning and scheduling, approximation algorithms, design and analysis of algorithms
1	Leslie Ann Goldberg, Paul W. Goldberg, Piotr Krysta, Carmine Ventre	Ranking games that have competitiveness-based strategies.	ACM Conference on Electronic Commerce	2010	DBLP DOI BibTeX RDF	anonymous games, computation of exact and approximate nash equilibria
1	Christopher Thomas Ryan, Albert Xin Jiang, Kevin Leyton-Brown	Computing pure strategy nash equilibria in compact symmetric games.	ACM Conference on Electronic Commerce	2010	DBLP DOI BibTeX RDF	rational generating functions, symmetric games, game theory
1	Prahladh Harsha, Adam Klivans, Raghu Meka	An invariance principle for polytopes.	STOC	2010	DBLP DOI BibTeX RDF	average sensitivity, invariance principles, polytopes, pseudorandom generators, contingency tables, noise sensitivity, limit theorems, agnostic learning
1	Daniel Lokshtanov, Jesper Nederlof	Saving space by algebraization.	STOC	2010	DBLP DOI BibTeX RDF	moebius, dynamic programming, space efficient, fourier
1	Gábor Ivanyos, Marek Karpinski, Nitin Saxena	Deterministic Polynomial Time Algorithms for Matrix Completion Problems.	Electronic Colloquium on Computational Complexity (ECCC)	2009	DBLP BibTeX RDF
1	Gábor Ivanyos, Marek Karpinski, Nitin Saxena	Deterministic Polynomial Time Algorithms for Matrix Completion Problems	CoRR	2009	DBLP BibTeX RDF
1	Philippe Baptiste, Marek Chrobak, Christoph Dürr	Polynomial Time Algorithms for Minimum Energy Scheduling	CoRR	2009	DBLP BibTeX RDF
1	Anders Gunnar, Mikael Johansson	Robust Load-balancing under Statistical Uncertainty: Models and Polynomial-time Algorithms.	NGI	2009	DBLP DOI BibTeX RDF
1	Felix Brandt, Markus Brill, Felix A. Fischer, Paul Harrenstein	Computational aspects of Shapley's saddles.	AAMAS	2009	DBLP DOI BibTeX RDF	Shapley's saddles, game theory, solution concepts
1	Hengwu Li	Approximation algorithm and scheme for RNA structure prediction.	Int. Conf. Interaction Sciences	2009	DBLP DOI BibTeX RDF	approximation algorithm, approximation scheme, RNA structure, pseudoknot
1	Dong-Hoon Shin, Saurabh Bagchi	Optimal monitoring in multi-channel multi-radio wireless mesh networks.	MobiHoc	2009	DBLP DOI BibTeX RDF	lp rounding, multi-channel multi-radio wireless networks, approximation algorithm, wireless mesh networks, security monitoring
1	Peng Sun, Ziyang Liu, Susan B. Davidson, Yi Chen	Detecting and resolving unsound workflow views for correct provenance analysis.	SIGMOD Conference	2009	DBLP DOI BibTeX RDF	workflow, view, provenance, soundness
1	Ioannis Caragiannis, Jason A. Covey, Michal Feldman, Christopher M. Homan, Christos Kaklamanis, Nikos Karanikolas, Ariel D. Procaccia, Jeffrey S. Rosenschein	On the approximability of Dodgson and Young elections.	SODA	2009	DBLP DOI BibTeX RDF
1	Ken-ichi Kawarabayashi, Bruce A. Reed	A nearly linear time algorithm for the half integral parity disjoint paths packing problem.	SODA	2009	DBLP DOI BibTeX RDF
1	Dániel Marx	Approximating fractional hypertree width.	SODA	2009	DBLP DOI BibTeX RDF
1	Michele Flammini, Alberto Marchetti-Spaccamela, Gianpiero Monaco, Luca Moscardelli, Shmuel Zaks	On the complexity of the regenerator placement problem in optical networks.	SPAA	2009	DBLP DOI BibTeX RDF	approximation algorithms, complexity, optical networks, wavelength division multiplexing (wdm), regenerators
1	Kousha Etessami, Mihalis Yannakakis	Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations.	J. ACM	2009	DBLP DOI BibTeX RDF	Recursive Markov chains, monotone nonlinear systems, multi-type branching processes, Newton's method, stochastic context-free grammars
1	Zhuowei Bao, Sarah Cohen Boulakia, Susan B. Davidson, Anat Eyal, Sanjeev Khanna	Differencing Provenance in Scientific Workflows.	ICDE	2009	DBLP DOI BibTeX RDF
1	Avigdor Gal, Maria Vanina Martinez, Gerardo I. Simari, V. S. Subrahmanian	Aggregate Query Answering under Uncertain Schema Mappings.	ICDE	2009	DBLP DOI BibTeX RDF
1	Jian-Jia Chen, Andreas Schranzhofer, Lothar Thiele	Energy minimization for periodic real-time tasks on heterogeneous processing units.	IPDPS	2009	DBLP DOI BibTeX RDF
1	Yigal Bejerano, Seung-Jae Han	Cell Breathing Techniques for Load Balancing in Wireless LANs.	IEEE Trans. Mob. Comput.	2009	DBLP DOI BibTeX RDF
1	John Case, Timo Kötzing	Difficulties in Forcing Fairness of Polynomial Time Inductive Inference.	ALT	2009	DBLP DOI BibTeX RDF
1	Hongfei Fu	Branching Bisimilarity between Finite-State Systems and BPA or Normed BPP Is Polynomial-Time Decidable.	APLAS	2009	DBLP DOI BibTeX RDF
1	Fanica Gavril	Algorithms on Subtree Filament Graphs.	Graph Theory, Computational Intelligence and Thought	2009	DBLP DOI BibTeX RDF	subtree filament graph, dominating hole, induced split subgraph, perfect graph
1	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
1	Francis Y. L. Chin, Hing-Fung Ting, Yong Zhang	Variable-Size Rectangle Covering.	COCOA	2009	DBLP DOI BibTeX RDF
1	Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara	Reconstruction of Interval Graphs.	COCOON	2009	DBLP DOI BibTeX RDF	the graph reconstruction conjecture, polynomial time algorithm, interval graphs
1	Michael R. Fellows, Tzvika Hartman, Danny Hermelin, Gad M. Landau, Frances A. Rosamond, Liat Rozenberg	Haplotype Inference Constrained by Plausible Haplotype Data.	CPM	2009	DBLP DOI BibTeX RDF
1	Stanislav Zivny, Peter G. Jeavons	The Complexity of Valued Constraint Models.	CP	2009	DBLP DOI BibTeX RDF
1	Franziska Berger, Peter Gritzmann, Sven de Vries	Minimum Cycle Bases and Their Applications.	Algorithmics of Large and Complex Networks	2009	DBLP DOI BibTeX RDF
1	Khaled M. Elbassioni, Kazuhisa Makino, Imran Rauf	Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs.	ESA	2009	DBLP DOI BibTeX RDF
1	Yossi Azar, Aleksander Madry, Thomas Moscibroda, Debmalya Panigrahi, Aravind Srinivasan	Maximum Bipartite Flow in Networks with Adaptive Channel Width.	ICALP	2009	DBLP DOI BibTeX RDF
1	Samir Khuller, Barna Saha	On Finding Dense Subgraphs.	ICALP	2009	DBLP DOI BibTeX RDF
1	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Yuri Pirola, Romeo Rizzi	Pure Parsimony Xor Haplotyping.	ISBRA	2009	DBLP DOI BibTeX RDF
1	Petr Skoda	Computability of Width of Submodular Partition Functions.	IWOCA	2009	DBLP DOI BibTeX RDF
1	Noga Alon, Shai Gutner	Balanced Hashing, Color Coding and Approximate Counting.	IWPEC	2009	DBLP DOI BibTeX RDF	Approximate counting of subgraphs, derandomization, expanders, perfect hashing, color-coding, k-wise independence
1	Michael Thomas	The Complexity of Circumscriptive Inference in Post's Lattice.	LPNMR	2009	DBLP DOI BibTeX RDF
1	Sagarmoy Dutta, Piyush P. Kurur	Representing Groups on Graphs.	MFCS	2009	DBLP DOI BibTeX RDF
1	Pedro Feijão, João Meidanis	SCJ: A Variant of Breakpoint Distance for Which Sorting, Genome Median and Genome Halving Problems Are Easy.	WABI	2009	DBLP DOI BibTeX RDF
1	Balasubramanian Sivan, S. Harini, C. Pandu Rangan	Core and Conditional Core Path of Specified Length in Special Classes of Graphs.	WALCOM	2009	DBLP DOI BibTeX RDF	Core path, Conditional core path, Bipartite permutation graphs, Threshold graphs, Proper Interval graphs
1	Martin Hoefer	Non-Cooperative Tree Creation.	Algorithmica	2009	DBLP DOI BibTeX RDF	Approximate Nash equilibrium, Connection game, Network design, Steiner tree, Price of anarchy
1	Thi Huyen Chau Nguyen, Pascal Richard, Enrico Bini	Approximation techniques for response-time analysis of static-priority tasks.	Real-Time Systems	2009	DBLP DOI BibTeX RDF	Uniprocessor real-time scheduling, Static-priority tasks, Approximation scheme, Worst-case response time
1	Yongpei Guan, Andrew J. Miller	Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems.	Operations Research	2008	DBLP DOI BibTeX RDF
1	Sriraman Sridharan	Polynomial time algorithms for two classes of subgraph problem.	RAIRO - Operations Research	2008	DBLP DOI BibTeX RDF
1	Alix Munier Kordon, Djamal Rebaine	Polynomial time algorithms for the UET permutation flowshop problem with time delays.	Computers & OR	2008	DBLP DOI BibTeX RDF
1	Frank Gurski	A comparison of two approaches for polynomial time algorithms computing basic graph parameters	CoRR	2008	DBLP BibTeX RDF
1	Viet Tung Hoang, Wing-Kin Sung	Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees	CoRR	2008	DBLP BibTeX RDF
1	Dorit S. Hochbaum	Polynomial time algorithms for bi-criteria, multi-objective and ratio problems in clustering and imaging. Part I: Normalized cut and ratio regions	CoRR	2008	DBLP BibTeX RDF
1	Viet Tung Hoang, Wing-Kin Sung	Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees.	STACS	2008	DBLP DOI BibTeX RDF
1	Emanuele Covino, Giovanni Pani, Daniele Scrimieri	Extending C++ Static Computation of Polynomial-Time Algorithms.	FCS	2008	DBLP BibTeX RDF
1	Dominique de Werra, Tamás Kis, Wieslaw Kubiak	Preemptive open shop scheduling with multiprocessors: polynomial cases and applications.	J. Scheduling	2008	DBLP DOI BibTeX RDF	Preemptive open shop scheduling, Multiprocessor operations, Polynomial time algorithms
1	Karthikeyan Sundaresan, Sampath Rangarajan	On exploiting diversity and spatial reuse in relay-enabled wireless networks.	MobiHoc	2008	DBLP DOI BibTeX RDF	wireless relay, scheduling, diversity, OFDMA, spatial reuse
1	Foto N. Afrati, Phokion G. Kolaitis	Answering aggregate queries in data exchange.	PODS	2008	DBLP DOI BibTeX RDF	data integration, data exchange, aggregate queries
1	Cédric Fournet, Tamara Rezk	Cryptographically sound implementations for typed information-flow security.	POPL	2008	DBLP DOI BibTeX RDF	probabilistic programs, cryptography, compilers, integrity, type systems, computational model, confidentiality, non-interference, secure information flow
1	Jin-yi Cai, Pinyan Lu	Holographic algorithms with unsymmetric signatures.	SODA	2008	DBLP DOI BibTeX RDF
1	Adrian Dumitrescu, Csaba D. Tóth	Minimum weight convex Steiner partitions.	SODA	2008	DBLP DOI BibTeX RDF
1	Marcelo Arenas, Leonid Libkin	XML data exchange: Consistency and query answering.	J. ACM	2008	DBLP DOI BibTeX RDF	computing certain answers, XML, consistency, Data exchange
1	Christos H. Papadimitriou, Tim Roughgarden	Computing correlated equilibria in multi-player games.	J. ACM	2008	DBLP DOI BibTeX RDF	Correlated equilibria, complexity of equilibria, Nash equilibria
1	Bruno Codenotti, Benton McCune, Sriram V. Pemmaraju, Rajiv Raman, Kasturi R. Varadarajan	An experimental study of different approaches to solve the market equilibrium problem.	ACM Journal of Experimental Algorithmics	2008	DBLP DOI BibTeX RDF	Market equilibrium
1	Peter Sanders, David Steurer	An asymptotic approximation scheme for multigraph edge coloring.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	chromatic index, data migration, Edge coloring, multigraphs
1	Weiyi Zhang, Guoliang Xue, Jian Tang, Krishnaiyan Thulasiraman	Faster algorithms for construction of recovery trees enhancing QoP and QoS.	IEEE/ACM Trans. Netw.	2008	DBLP DOI BibTeX RDF	protection and restoration, quality of protection (QoP), redundant trees, quality of service (QoS), bottleneck bandwidth
1	Parikshit Gopalan, Venkatesan Guruswami	Hardness Amplification within NP against Deterministic Algorithms.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	Hardness Amplication, Error-Correcting Codes, Derandomization, NP