Search results for "Polynomial-space"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
38	Yoshio Okamoto, Takeaki Uno	A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization.	ISAAC	2007	DBLP DOI BibTeX RDF
37	Hiroki Arimura, Takeaki Uno, Shinichi Shimozono	Time and Space Efficient Discovery of Maximal Geometric Graphs.	Discovery Science	2007	DBLP DOI BibTeX RDF	closed graph mining, rightmost expansion, polynomial delay polynomial space enumeration algorithms, depth-first search, geometric graphs
32	Daniel Lokshtanov, Jesper Nederlof	Saving space by algebraization.	STOC	2010	DBLP DOI BibTeX RDF	moebius, dynamic programming, space efficient, fourier
28	Hiroki Arimura, Takeaki Uno	An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Maximal motif, Data mining, Algorithm, Delay, Polynomial time, Pattern discovery, Enumeration, Motif, Sequence mining, Closed pattern, Closed itemset
28	Hiroki Arimura, Takeaki Uno	A Polynomial Space and Polynomial Delay Algorithm for Enumeration of Maximal Motifs in a Sequence.	ISAAC	2005	DBLP DOI BibTeX RDF
26	Vítezslav Svejdar	On the polynomial-space completeness of intuitionistic propositional logic.	Arch. Math. Log.	2003	DBLP DOI BibTeX RDF	Logical connectives, Intuitionistic logic, Decision problem, Non-classical logics, Kripke models, Polynomial-space
26	Takashi Katoh, Hiroki Arimura, Kouichi Hirata	A Polynomial-Delay Polynomial-Space Algorithm for Extracting Frequent Diamond Episodes from Event Sequences.	PAKDD	2009	DBLP DOI BibTeX RDF
24	Peter Bürgisser, Martin Lotz	The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties.	Found. Comput. Math.	2007	DBLP DOI BibTeX RDF
22	Marco Gaboardi, Jean-Yves Marion, Simona Ronchi Della Rocca	A logical account of pspace.	POPL	2008	DBLP DOI BibTeX RDF	type assignment, linear logic, implicit computational complexity, polynomial space
22	Fedor V. Fomin, Fabrizio Grandoni 0001, Dieter Kratsch	Faster Steiner Tree Computation in Polynomial-Space.	ESA	2008	DBLP DOI BibTeX RDF
21	Peter Clote	A Time-Space Hierarchy Between Polynomial Time and Polynomial Space.	Math. Syst. Theory	1992	DBLP DOI BibTeX RDF
21	Shimon Even, Robert Endre Tarjan	A Combinatorial Problem Which Is Complete in Polynomial Space.	J. ACM	1976	DBLP DOI BibTeX RDF
21	Andrzej Lingas	A PSPACE Complete Problem Related to a Pebble Game.	ICALP	1978	DBLP DOI BibTeX RDF	dag, completeness in polynomial space, computational complexity, PSPACE, pebble game, AND/OR graph
20	Jesper Nederlof	Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems.	ICALP (1)	2009	DBLP DOI BibTeX RDF
19	Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos	On Exact Algorithms for Treewidth.	ESA	2006	DBLP DOI BibTeX RDF
19	Yu Huang, Guozhao Wang	An orthogonal basis for the hyperbolic hybrid polynomial space.	Sci. China Ser. F Inf. Sci.	2007	DBLP DOI BibTeX RDF	H-Bézier basis, orthogonal basis, basis transformations, degree reduction
19	Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto	Computing the Tutte Polynomial in Vertex-Exponential Time.	FOCS	2008	DBLP DOI BibTeX RDF
18	Lance Fortnow, Carsten Lund	Interactive Proof Systems and Alternating Time-Space Complexity.	STACS	1991	DBLP DOI BibTeX RDF
17	Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa	Polynomial-Delay and Polynomial-Space Enumeration of Large Maximal Matchings.	WG	2022	DBLP DOI BibTeX RDF
17	Amir M. Ben-Amram, Geoff W. Hamilton	Tight Polynomial Bounds for Loop Programs in Polynomial Space.	Log. Methods Comput. Sci.	2021	DBLP DOI BibTeX RDF
17	Amir M. Ben-Amram, Geoff W. Hamilton	Tight Polynomial Bounds for Loop Programs in Polynomial Space.	CoRR	2020	DBLP BibTeX RDF
17	Noriyuki Fujimoto	A Pseudo-Polynomial Time Algorithm for Solving the Knapsack Problem in Polynomial Space.	COCOA	2016	DBLP DOI BibTeX RDF
17	Yoshio Okamoto, Takeaki Uno	A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization.	Eur. J. Oper. Res.	2011	DBLP DOI BibTeX RDF
17	Hiroki Arimura, Takeaki Uno	Polynomial-Delay and Polynomial-Space Algorithms for Mining Closed Sequences, Graphs, and Pictures in Accessible Set Systems.	SDM	2009	DBLP DOI BibTeX RDF
17	Karl-Heinz Niggl, Henning Wunderlich	Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs.	SIAM J. Comput.	2006	DBLP DOI BibTeX RDF
17	Leslie Ann Goldberg	Polynomial space polynomial delay algorithms for listing families of graphs.	STOC	1993	DBLP DOI BibTeX RDF
17	Harold M. Hastings	Maps of the interval, polynomial time, and polynomial space.	SIGACT News	1985	DBLP DOI BibTeX RDF
15	Andreas Björklund, Thore Husfeldt	Inclusion--Exclusion Algorithms for Counting Set Partitions.	FOCS	2006	DBLP DOI BibTeX RDF
15	Mihalis Yannakakis, Kousha Etessami	Checking LTL Properties of Recursive Markov Chains.	QEST	2005	DBLP DOI BibTeX RDF
15	Vítezslav Svejdar	The decision problem of provability logic with only one atom.	Arch. Math. Log.	2003	DBLP DOI BibTeX RDF	Provability logic, Propositional atoms, Non-classical logics, Kripke models, Polynomial-space
15	Harry Buhrman, Lance Fortnow, Leen Torenvliet	Using Autoreducibility to Separate Complexity Classes.	FOCS	1995	DBLP DOI BibTeX RDF	autoreducibility, doubly exponential space, Turing complete sets, logarithmic space, computational complexity, set theory, oracle, complexity theory, Turing machines, Turing machine, complexity classes, structural properties, polynomial space, diagonalization
15	Rajamani Sundar	A Lower Bound for the Dictionary Problem under a Hashing Model	FOCS	1991	DBLP DOI BibTeX RDF	randomized complexities, update costs, deterministic complexities, constant amortized time, multilevel hashing model, log-algorithmic amortized time, nontrivial lower bound, limited wordsize, memory locations, data structures, polynomial space, dictionary problem, cell probe model
15	Adi Shamir	IP=PSPACE	FOCS	1990	DBLP DOI BibTeX RDF	acceptance probability, honest provers, public coins, logarithmic workspace, two-way access, random tape, interaction, IP, randomization, polynomial time, one-way functions, zero-knowledge proofs, interactive proofs, PSPACE, polynomial space, proof verification
15	Takumi Kasai, Akeo Adachi, Shigeki Iwata	Classes of pebble games and complete problems.	ACM Annual Conference (2)	1978	DBLP DOI BibTeX RDF	Exponential time, Log-space, Two-person game, Winning strategy, Polynomial time, Turing machine, NP, Pebble game, Polynomial space
15	Rida T. Farouki, Takis Sakkalis	Pythagorean-hodograph space curves.	Adv. Comput. Math.	1994	DBLP DOI BibTeX RDF	Pythagorean hodograph, arc length, canal surface, Space curve, helix
15	Mihai Patrascu, Mikkel Thorup	Randomization does not help searching predecessors.	SODA	2007	DBLP BibTeX RDF
14	Brandon Blakeley, Francine Blanchet-Sadri, Josh Gunter, Narad Rampersad	On the Complexity of Deciding Avoidability of Sets of Partial Words.	Developments in Language Theory	2009	DBLP DOI BibTeX RDF
14	Anton Chechetka, Katia P. Sycara	No-commitment branch and bound search for distributed constraint optimization.	AAMAS	2006	DBLP DOI BibTeX RDF	cooperative distributed problem solving in agent system
13	Arne Andersson, Mikkel Thorup	Dynamic ordered sets with exponential search trees.	J. ACM	2007	DBLP DOI BibTeX RDF	ordered lists, Search trees
13	María López-Valdés, Elvira Mayordomo	Dimension Is Compression.	MFCS	2005	DBLP DOI BibTeX RDF
13	Franz-Josef Brandenburg	On the Height of Syntactical Graphs.	Theoretical Computer Science	1981	DBLP DOI BibTeX RDF
12	John H. Reif, Micha Sharir	Motion Planning in the Presence of Moving Obstacles.	J. ACM	1994	DBLP DOI BibTeX RDF	moving obstacles, theory of reals, computational geometry, motion planning, decision procedures, Turing machines, cylindrical algebraic decomposition
12	Dieter Spreen	On Functions Computable in Nondeterministic Polynomial Time: Some Characterizations.	CSL	1987	DBLP DOI BibTeX RDF
12	Mihai Patrascu, Mikkel Thorup	Higher Lower Bounds for Near-Neighbor and Further Rich Problems.	FOCS	2006	DBLP DOI BibTeX RDF
12	Gunar Matthies, Lutz Tobiska	The Inf-Sup Condition for the Mapped Qk-Pk-1disc Element in Arbitrary Space Dimensions.	Computing	2002	DBLP DOI BibTeX RDF	AMS Subject Classifications:65N12, 65N30
12	Rina Panigrahy, Kunal Talwar, Udi Wieder	A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match.	FOCS	2008	DBLP DOI BibTeX RDF
11	Ruzica Piskac, Viktor Kuncak	Decision Procedures for Multisets with Cardinality Constraints.	VMCAI	2008	DBLP DOI BibTeX RDF
11	Caroline Brosse, Alessio Conte, Vincent Limouzy, Giulia Punzi, Davide Rucci	Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space.	CoRR	2024	DBLP DOI BibTeX RDF
11	Flavio Ferrarotti, Klaus-Dieter Schewe	Choiceless Polynomial Space.	CoRR	2024	DBLP DOI BibTeX RDF
11	Jesper Nederlof, Michal Pilipczuk, Céline M. F. Swennenhuis, Karol Wegrzycki	Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space.	SIAM J. Discret. Math.	2023	DBLP DOI BibTeX RDF
11	Kyungrok Lee, Jung-Il Choi, Jungho Yoon	Improving the third-order WENO schemes by using exponential polynomial space with a locally optimized shape parameter.	Comput. Math. Appl.	2023	DBLP DOI BibTeX RDF
11	Serge Gaspers, Edward J. Lee	Faster Graph Coloring in Polynomial Space.	Algorithmica	2023	DBLP DOI BibTeX RDF
11	Wojciech Nadara, Michal Pilipczuk, Marcin Smulewicz	Computing treedepth in polynomial space and linear fpt time.	CoRR	2022	DBLP DOI BibTeX RDF
11	David P. Woodruff, Taisuke Yasuda 0002	High-Dimensional Geometric Streaming in Polynomial Space.	CoRR	2022	DBLP DOI BibTeX RDF
11	David P. Woodruff, Taisuke Yasuda 0002	High-Dimensional Geometric Streaming in Polynomial Space.	FOCS	2022	DBLP DOI BibTeX RDF
11	Wojciech Nadara, Michal Pilipczuk, Marcin Smulewicz	Computing Treedepth in Polynomial Space and Linear FPT Time.	ESA	2022	DBLP DOI BibTeX RDF
11	Shicang Song, Lijuan Lu	A nonconforming scheme with piecewise quasi three degree polynomial space to solve biharmonic problem.	J. Appl. Math. Comput.	2021	DBLP DOI BibTeX RDF
11	Daniel Lokshtanov, Andreas Björklund, Saket Saurabh 0001, Meirav Zehavi	Approximate Counting of k-Paths: Simpler, Deterministic, and in Polynomial Space.	ACM Trans. Algorithms	2021	DBLP DOI BibTeX RDF
11	Xin Ye, Yuanzhe Xi, Yousef Saad	Proxy-GMRES: Preconditioning via GMRES in Polynomial Space.	SIAM J. Matrix Anal. Appl.	2021	DBLP DOI BibTeX RDF
11	Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar 0002, Saket Saurabh 0001	ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space.	CoRR	2021	DBLP BibTeX RDF
11	Andreas Björklund	An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs.	STACS	2021	DBLP DOI BibTeX RDF
11	Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar 0002, Saket Saurabh 0001	ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space.	FSTTCS	2021	DBLP DOI BibTeX RDF
11	Saulo Queiroz, Wesley Silva, João P. Vilela, Edmundo Monteiro	Maximal Spectral Efficiency of OFDM With Index Modulation Under Polynomial Space Complexity.	IEEE Wirel. Commun. Lett.	2020	DBLP DOI BibTeX RDF
11	Andreas Björklund	An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs.	CoRR	2020	DBLP BibTeX RDF
11	Falko Hegerfeld, Stefan Kratsch	Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space.	CoRR	2020	DBLP BibTeX RDF
11	Jesper Nederlof, Michal Pilipczuk, Céline M. F. Swennenhuis, Karol Wegrzycki	Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space.	CoRR	2020	DBLP BibTeX RDF
11	Jesper Nederlof, Michal Pilipczuk, Céline M. F. Swennenhuis, Karol Wegrzycki	Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space.	WG	2020	DBLP DOI BibTeX RDF
11	Falko Hegerfeld, Stefan Kratsch	Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space.	STACS	2020	DBLP DOI BibTeX RDF
11	Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh 0001	Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree.	SIAM J. Discret. Math.	2019	DBLP DOI BibTeX RDF
11	Saulo Queiroz, Wesley Silva, João P. Vilela, Edmundo Monteiro	Maximal Spectral Efficiency of OFDM with Index Modulation under Polynomial Space Complexity.	CoRR	2019	DBLP BibTeX RDF
11	Andreas Björklund, Daniel Lokshtanov, Saket Saurabh 0001, Meirav Zehavi	Approximate Counting of k-Paths: Deterministic and in Polynomial Space.	ICALP	2019	DBLP DOI BibTeX RDF
11	Mohd Shahrizan Othman, Aleksandar Shurbevski, Hiroshi Nagamochi	Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem.	IEICE Trans. Inf. Syst.	2018	DBLP DOI BibTeX RDF
11	Gregory Z. Gutin, Felix Reidl, Magnus Wahlström, Meirav Zehavi	Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials.	J. Comput. Syst. Sci.	2018	DBLP DOI BibTeX RDF
11	Norhazwani Md Yunos, Aleksandar Shurbevski, Hiroshi Nagamochi	An Improved-time Polynomial-space Exact Algorithm for TSP in Degree-5 Graphs.	J. Inf. Process.	2017	DBLP DOI BibTeX RDF
11	Lehel Banjai, Emmanuil H. Georgoulis, Oluwaseun Lijoka	A Trefftz Polynomial Space-Time Discontinuous Galerkin Method for the Second Order Wave Equation.	SIAM J. Numer. Anal.	2017	DBLP DOI BibTeX RDF
11	Serge Gaspers, Gregory B. Sorkin	Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.	ACM Trans. Algorithms	2017	DBLP DOI BibTeX RDF
11	Gregory Z. Gutin, Felix Reidl, Magnus Wahlström, Meirav Zehavi	Kirchoff Matrices and Pfaffians to Design Deterministic Polynomial-Space Parameterized Algorithms.	CoRR	2017	DBLP BibTeX RDF
11	Diego Figueira, Ranko Lazic 0001, Jérôme Leroux, Filip Mazowiecki, Grégoire Sutre	Polynomial-Space Completeness of Reachability for Succinct Branching VASS in Dimension One.	ICALP	2017	DBLP DOI BibTeX RDF
11	Serge Gaspers, Edward J. Lee	Faster Graph Coloring in Polynomial Space.	COCOON	2017	DBLP DOI BibTeX RDF
11	Norhazwani Md Yunos	Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs.		2017	RDF
11	Keith J. Edwards	A faster polynomial-space algorithm for Max 2-CSP.	J. Comput. Syst. Sci.	2016	DBLP DOI BibTeX RDF
11	Serge Gaspers, Edward J. Lee	Faster Graph Coloring in Polynomial Space.	CoRR	2016	DBLP BibTeX RDF
11	Olivier Kihl, David Picard, Philippe Henri Gosselin	Local polynomial space-time descriptors for action classification.	Mach. Vis. Appl.	2016	DBLP DOI BibTeX RDF
11	Xiang Huang 0001, Donald M. Stull	Polynomial Space Randomness in Analysis.	MFCS	2016	DBLP DOI BibTeX RDF
11	Dimitri Watel, Marc-Antoine Weisser, Cédric Bentz, Dominique Barth	An FPT algorithm in polynomial space for the Directed Steiner Tree problem with Limited number of Diffusing nodes.	Inf. Process. Lett.	2015	DBLP DOI BibTeX RDF
11	Mark van Hoeij	Groebner basis in Boolean rings is not polynomial-space.	CoRR	2015	DBLP BibTeX RDF
11	Xiang Huang 0001, Donald M. Stull	Polynomial Space Randomness in Analysis with Application to the Lebesgue Differentiation Theorem.	CoRR	2015	DBLP BibTeX RDF
11	Natarajan Shankar, K. Subramani 0001, Pavlos Eirinakis	Identifying Negative Cost Cycles in Strongly Polynomial Space.	Nord. J. Comput.	2015	DBLP BibTeX RDF
11	Norhazwani Md Yunos, Aleksandar Shurbevski, Hiroshi Nagamochi	A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs.	JCDCGG	2015	DBLP DOI BibTeX RDF
11	Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh 0001	Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree.	ICALP (1)	2015	DBLP DOI BibTeX RDF
11	Serge Gaspers, Gregory B. Sorkin	Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.	ICALP (1)	2015	DBLP DOI BibTeX RDF
11	Bogdan Aman, Gabriel Ciobanu	Natural Computing Modelling of the Polynomial Space Turing Machines.	ICTERI	2015	DBLP BibTeX RDF
11	Satoru Sakai, Masakazu Sato	Visual Systems & Control on Polynomial Space and Its Application to Sloshing Problems.	IEEE Trans. Control. Syst. Technol.	2014	DBLP DOI BibTeX RDF
11	Jesper Nederlof	Fast Polynomial-Space Algorithms Using Inclusion-Exclusion.	Algorithmica	2013	DBLP DOI BibTeX RDF
11	Fedor V. Fomin, Fabrizio Grandoni 0001, Dieter Kratsch, Daniel Lokshtanov, Saket Saurabh 0001	Computing Optimal Steiner Trees in Polynomial Space.	Algorithmica	2013	DBLP DOI BibTeX RDF
11	Simone Bova, Franco Montagna	Polynomial space hardness without disjunction property.	Theor. Comput. Sci.	2013	DBLP DOI BibTeX RDF
11	Daniel Dadush	A Deterministic Polynomial Space Construction for eps-nets under any Norm.	CoRR	2013	DBLP BibTeX RDF
11	Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Pawel Rzazewski	Determining the L(2, 1)L(2, 1)-span in polynomial space.	Discret. Appl. Math.	2013	DBLP DOI BibTeX RDF
11	Rida T. Farouki, Takis Sakkalis	Corrigendum to "Rational rotation-minimizing frames on polynomial space curves of arbitrary degree" [J. Symbolic Comput. 45(8) (2010) 844-856].	J. Symb. Comput.	2013	DBLP DOI BibTeX RDF
11	Olivier Kihl, David Picard, Philippe Henri Gosselin	Local polynomial space-time descriptors for actions classification.	MVA	2013	DBLP BibTeX RDF