Search results for "bounded-width"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
67	Farid M. Ablayev, Cristopher Moore, Chris Pollett	Quantum and Stochastic Branching Programs of Bounded Width.	ICALP	2002	DBLP DOI BibTeX RDF
64	Dániel Marx	Approximating fractional hypertree width.	SODA	2009	DBLP DOI BibTeX RDF
43	Libor Barto, Marcin Kozik	Constraint Satisfaction Problems of Bounded Width.	FOCS	2009	DBLP DOI BibTeX RDF	bounded width, constraint satisfaction problem, local consistency
41	Christoph Meinel	Omega-Branching Programs of Bounded Width.	CSL	1989	DBLP DOI BibTeX RDF
40	Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer	DAG-Width and Parity Games.	STACS	2006	DBLP DOI BibTeX RDF
36	Mukul R. Prasad, Philip Chong, Kurt Keutzer	Why is Combinational ATPG Efficiently Solvable for Practical VLSI Circuits?	J. Electron. Test.	2001	DBLP DOI BibTeX RDF	combinational ATPG, SAT, backtracking, complexity analysis, VLSI circuits
36	Masaki Nakanishi, Kiyoharu Hamaguchi, Toshinobu Kashiwabara	Ordered Quantum Branching Programs Are More Powerful than Ordered Probabilistic Branching Programs under a Bounded-Width Restriction.	COCOON	2000	DBLP DOI BibTeX RDF
33	Petr Hlinený	Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids.	STACS	2003	DBLP DOI BibTeX RDF	representable matroid, fixed-parameter complexity, Classification: parametrized complexity and logic in computer science. (Math subjects 05B35, 68R05, 03D05.), monadic second-order logic, branch-width
31	Michael T. Hallett, Jens Lagergren	New algorithms for the duplication-loss model.	RECOMB	2000	DBLP DOI BibTeX RDF
28	Slawomir Lasota 0001	Bounded width = strict width 2, for coset templates.	CoRR	2014	DBLP BibTeX RDF
27	Rodney G. Downey, Catherine McCartin	Online Problems, Pathwidth, and Persistence.	IWPEC	2004	DBLP DOI BibTeX RDF
27	Nicolas Bedon	Logic and Bounded-Width Rational Languages of Posets over Countable Scattered Linear Orderings.	LFCS	2009	DBLP DOI BibTeX RDF
26	David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum	On Monotone Planar Circuits.	CCC	1999	DBLP DOI BibTeX RDF
25	Jin-yi Cai, Richard J. Lipton	Subquadratic Simulations of Circuits by Branching Programs	FOCS	1989	DBLP DOI BibTeX RDF	group-theoretic results, subquadratic simulations, simulations of circuits, bounded-width, branching programs, Boolean circuits
25	David R. Wood, Jan Arne Telle	Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor.	GD	2006	DBLP DOI BibTeX RDF
25	Igor Razgon	The splitting power of branching programs of bounded repetition and CNFs of bounded width.	CoRR	2022	DBLP BibTeX RDF
25	Albert Atserias	The Proof-Search Problem between Bounded-Width Resolution and Bounded-Degree Semi-algebraic Proofs.	SAT	2013	DBLP DOI BibTeX RDF
22	Martin Fürer, Shiva Prasad Kasiviswanathan	Approximately Counting Embeddings into Random Graphs.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
18	Daniel Sawitzki	A Symbolic Approach to the All-Pairs Shortest-Paths Problem.	WG	2004	DBLP DOI BibTeX RDF
18	Dmitry N. Kozlov	Maximizing the Möbius Function of a Poset and the Sum of the Betti Numbers of the Order Complex.	Comb.	1999	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 06A07, 05E25, 05D99
18	Michal Wrona	Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation).	CoRR	2024	DBLP DOI BibTeX RDF
18	Andreas Emil Feldmann, Michael Lampis	Parameterized Algorithms for Steiner Forest in Bounded Width Graphs.	CoRR	2024	DBLP DOI BibTeX RDF
18	Jason Gaitonde, Elchanan Mossel	A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width.	CoRR	2023	DBLP DOI BibTeX RDF
18	Hiroki Morizumi	An Approach to Circuit Lower Bounds via Bounded Width Circuits.	CoRR	2023	DBLP DOI BibTeX RDF
18	Nabil Adrar, Philippe Jégou, Cyril Terrioux	Computing partial hypergraphs of bounded width.	Discret. Appl. Math.	2023	DBLP DOI BibTeX RDF
18	Dominik Drexler, Jendrik Seipp, Hector Geffner	Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Version.	CoRR	2022	DBLP DOI BibTeX RDF
18	Dominik Drexler, Jendrik Seipp, Hector Geffner	Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width.	ICAPS	2022	DBLP BibTeX RDF
18	Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, Amir Nayyeri	Low-stretch spanning trees of graphs with bounded width.	CoRR	2020	DBLP BibTeX RDF
18	Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, Amir Nayyeri	Low-Stretch Spanning Trees of Graphs with Bounded Width.	SWAT	2020	DBLP DOI BibTeX RDF
18	Klaus Jansen, Malin Rau	Improved approximation for two dimensional Strip Packing with polynomial bounded width.	Theor. Comput. Sci.	2019	DBLP DOI BibTeX RDF
18	Zarathustra Brady	Examples, counterexamples, and structure in bounded width algebras.	CoRR	2019	DBLP BibTeX RDF
18	Andrew Gorczyca, Audrey Decker	Distributed Ledger Witness Selection in Bounded Width Directed Acyclic Graphs.	IEEE ICBC	2019	DBLP DOI BibTeX RDF
18	Stephan Kreutzer, O-joung Kwon	Digraphs of Bounded Width.	Classes of Directed Graphs	2018	DBLP DOI BibTeX RDF
18	Kolja Knauer, Piotr Micek, Torsten Ueckerdt	The Queue-Number of Posets of Bounded Width or Height.	GD	2018	DBLP DOI BibTeX RDF
18	Boris Hanin	Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations.	CoRR	2017	DBLP BibTeX RDF
18	Klaus Jansen, Malin Rau	Improved Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width.	WALCOM	2017	DBLP DOI BibTeX RDF
18	Marcin Kozik	Weaker consistency notions for all the CSPs of bounded width.	CoRR	2016	DBLP BibTeX RDF
18	Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop	Nested Weighted Limit-Average Automata of Bounded Width.	CoRR	2016	DBLP BibTeX RDF
18	Klaus Jansen, Malin Rau	Improved approximation for two dimensional strip packing with polynomial bounded width.	CoRR	2016	DBLP BibTeX RDF
18	Libor Barto	The collapse of the bounded width hierarchy.	J. Log. Comput.	2016	DBLP DOI BibTeX RDF
18	Marcin Kozik	Weak consistency notions for all the CSPs of bounded width.	LICS	2016	DBLP DOI BibTeX RDF
18	Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop	Nested Weighted Limit-Average Automata of Bounded Width.	MFCS	2016	DBLP DOI BibTeX RDF
18	Jakub Gajarský, Petr Hlinený, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan 0001, Saket Saurabh 0001	FO Model Checking on Posets of Bounded Width.	CoRR	2015	DBLP BibTeX RDF
18	Yoichi Iwata, Yuichi Yoshida	On the Equivalence among Problems of Bounded Width.	CoRR	2015	DBLP BibTeX RDF
18	Jakub Gajarský, Petr Hlinený, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan 0001, Saket Saurabh 0001	FO Model Checking on Posets of Bounded Width.	FOCS	2015	DBLP DOI BibTeX RDF
18	Yoichi Iwata, Yuichi Yoshida	On the Equivalence among Problems of Bounded Width.	ESA	2015	DBLP DOI BibTeX RDF
18	Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan 0001	Metric Dimension of Bounded Width Graphs.	MFCS (2)	2015	DBLP DOI BibTeX RDF
18	Albert Atserias, Sergi Oliva	Bounded-width QBF is PSPACE-complete.	J. Comput. Syst. Sci.	2014	DBLP DOI BibTeX RDF
18	Albert Atserias, Johannes Klaus Fichte, Marc Thurley	Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution.	CoRR	2014	DBLP BibTeX RDF
18	Héctor Palacios, Hector Geffner	Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width.	CoRR	2014	DBLP BibTeX RDF
18	Elisabeth Günther, Felix G. König, Nicole Megow	Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width.	J. Comb. Optim.	2014	DBLP DOI BibTeX RDF
18	Ioannis Katsikarelis	Computing bounded-width tree and branch decompositions of k-outerplanar graphs	CoRR	2013	DBLP BibTeX RDF
18	Albert Atserias, Sergi Oliva	Bounded-width QBF is PSPACE-complete.	STACS	2013	DBLP DOI BibTeX RDF
18	Albert Atserias, Sergi Oliva	Bounded-width QBF is PSPACE-complete.	Electron. Colloquium Comput. Complex.	2012	DBLP BibTeX RDF
18	Albert Atserias, Johannes Klaus Fichte, Marc Thurley	Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution.	J. Artif. Intell. Res.	2011	DBLP DOI BibTeX RDF
18	Leo Liberti, Benoît Masson, Carlile Lavor, Antonio Mucherino	Branch-and-Prune trees with bounded width.	CTW	2011	DBLP BibTeX RDF
18	Benoît Larose, Matthew Valeriote, László Zádori	Omitting Types, Bounded Width and the Ability to Count.	Int. J. Algebra Comput.	2009	DBLP DOI BibTeX RDF
18	Héctor Palacios, Hector Geffner	Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width.	J. Artif. Intell. Res.	2009	DBLP DOI BibTeX RDF
18	Libor Barto, Marcin Kozik	Congruence Distributivity Implies Bounded Width.	SIAM J. Comput.	2009	DBLP DOI BibTeX RDF
18	Albert Atserias, Johannes Klaus Fichte, Marc Thurley	Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution.	SAT	2009	DBLP DOI BibTeX RDF
18	Elisabeth Günther, Felix G. König, Nicole Megow	Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width.	WAOA	2009	DBLP DOI BibTeX RDF
18	Zeev Nutov, Daniel Reichman 0001	Approximating maximum satisfiable subsystems of linear equations of bounded width.	Inf. Process. Lett.	2008	DBLP DOI BibTeX RDF
18	Catarina Carvalho, Víctor Dalmau, Petar Markovic, Miklós Maróti	CD(4) has bounded width	CoRR	2007	DBLP BibTeX RDF
18	Chris Pollett, Farid M. Ablayev, Cristopher Moore	Quantum and Stochastic Programs of Bounded Width	Electron. Colloquium Comput. Complex.	2002	DBLP BibTeX RDF
18	Rustam Mubarakzjanov	Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable	Electron. Colloquium Comput. Complex.	2001	DBLP BibTeX RDF
18	Kamal Lodaya, Pascal Weil	Series-parallel languages and the bounded-width property.	Theor. Comput. Sci.	2000	DBLP DOI BibTeX RDF
18	Atsuyoshi Nakamura	Query learning of bounded-width OBDDs.	Theor. Comput. Sci.	2000	DBLP DOI BibTeX RDF
18	Atsuyoshi Nakamura	Query Learning of Bounded-Width OBDDs.	ALT	1996	DBLP DOI BibTeX RDF
18	David A. Mix Barrington, Howard Straubing	Superlinear Lower Bounds for Bounded-Width Branching Programs.	J. Comput. Syst. Sci.	1995	DBLP DOI BibTeX RDF
18	Funda Ergün, Ravi Kumar 0001, Ronitt Rubinfeld	On Learning Bounded-Width Branching Programs.	COLT	1995	DBLP DOI BibTeX RDF
18	Sorin Istrail, Dejan Zivkovic	Bounded-Width Polynomial-Size Boolean Formulas Compute Exactly Those Functions in AC^0.	Inf. Process. Lett.	1994	DBLP DOI BibTeX RDF
18	Emanuel Knill	Families of sets with locally bounded width.	Graphs Comb.	1994	DBLP DOI BibTeX RDF
18	Hans L. Bodlaender, Michael R. Fellows, Michael T. Hallett	Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy.	STOC	1994	DBLP DOI BibTeX RDF
18	Richard Cleve	Towards Optimal Simulations of Formulas by Bounded-Width Programs.	Comput. Complex.	1991	DBLP DOI BibTeX RDF
18	David A. Mix Barrington, Howard Straubing	Superlinear Lower Bounds for Bounded-Width Branching Programs.	SCT	1991	DBLP DOI BibTeX RDF
18	Richard Cleve	Towards Optimal Simulations of Formulas by Bounded-Width Programs	STOC	1990	DBLP DOI BibTeX RDF
18	David A. Mix Barrington	Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹.	J. Comput. Syst. Sci.	1989	DBLP DOI BibTeX RDF
18	Bruno Courcelle	The Monadic Second-Order Logic of Graphs, II: Infinite Graphs of Bounded Width.	Math. Syst. Theory	1989	DBLP DOI BibTeX RDF
18	Christoph Meinel	The Power of Nondeterminism in Polynomial-Size Bounded-Width Branching Programs.	Theor. Comput. Sci.	1988	DBLP DOI BibTeX RDF
18	Christoph Meinel	The Power of Nondeterminism in Polynominal-size Bounded-width Branching Programs.	FCT	1987	DBLP DOI BibTeX RDF
18	David A. Mix Barrington	Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹	STOC	1986	DBLP DOI BibTeX RDF
16	Luca Trevisan	Non-approximability results for optimization problems on bounded degree instances.	STOC	2001	DBLP DOI BibTeX RDF
15	Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao	Arithmetizing Classes Around NC 1 and L.	STACS	2007	DBLP DOI BibTeX RDF
13	Alexander Grigoriev, Gerhard J. Woeginger	Project scheduling with irregular costs: complexity, approximability, and algorithms.	Acta Informatica	2004	DBLP DOI BibTeX RDF
13	Alexander Grigoriev, Gerhard J. Woeginger	Project Scheduling with Irregular Costs: Complexity, Approximability, and Algorithms.	ISAAC	2002	DBLP DOI BibTeX RDF
13	Christos H. Papadimitriou, Mihalis Yannakakis	Shortest Paths Without a Map.	ICALP	1989	DBLP DOI BibTeX RDF
9	Gábor Kun, Mario Szegedy	A new line of attack on the dichotomy conjecture.	STOC	2009	DBLP DOI BibTeX RDF	term operations, computational complexity, constraint satisfaction problems, fourier analysis, NP, dichotomy
9	Liliana Cojocaru	Branching Programs, Grammar Systems and the NC1 Class.	SYNASC	2007	DBLP DOI BibTeX RDF
9	Emil W. Kiss, Matthew Valeriote	On Tractability and Congruence Distributivity.	LICS	2006	DBLP DOI BibTeX RDF
9	Clemens Lautemann, Pascal Tesson, Denis Thérien	An Algebraic Point of View on the Crane Beach Property.	CSL	2006	DBLP DOI BibTeX RDF
9	Dietmar Berwanger, Erich Grädel	Fixed-Point Logics and Solitaire Games.	Theory Comput. Syst.	2004	DBLP DOI BibTeX RDF
9	Wim Martens, Frank Neven	Typechecking Top-Down Uniform Unranked Tree Transducers.	ICDT	2003	DBLP DOI BibTeX RDF
9	Khaled M. Elbassioni	An Algorithm for Dualization in Products of Lattices and Its Applications.	ESA	2002	DBLP DOI BibTeX RDF
9	Renaud Lepère, Denis Trystram, Gerhard J. Woeginger	Approximation Algorithms for Scheduling Malleable Tasks under Precedence Constraints.	ESA	2001	DBLP DOI BibTeX RDF
9	Christof Löding, Wolfgang Thomas	Alternating Automata and Logics over Infinite Words.	IFIP TCS	2000	DBLP DOI BibTeX RDF
9	Erich Grädel, Igor Walukiewicz	Guarded Fixed Point Logic.	LICS	1999	DBLP DOI BibTeX RDF
9	Pierre McKenzie, Klaus Reinhardt, V. Vinay	Circuits and Context-Free Languages.	COCOON	1999	DBLP DOI BibTeX RDF
9	Kamal Lodaya, Pascal Weil	Series-Parallel Posets: Algebra, Automata and Languages.	STACS	1998	DBLP DOI BibTeX RDF
9	David A. Mix Barrington, Denis Thérien	Finite monoids and the fine structure of NC1.	J. ACM	1988	DBLP DOI BibTeX RDF