Search results for "Treewidth"

Hits ?▲	Authors	Title	Venue	Year	Link
15	K. S. Sesh Kumar, Francis R. Bach	Convex Relaxations for Learning Bounded Treewidth Decomposable Graphs	CoRR	2012	DBLP BibTeX RDF
15	L. Sunil Chandran, Rogers Mathew, Deepak Rajendraprasad, Roohani Sharma	Product Dimension of Forests and Bounded Treewidth Graphs	CoRR	2012	DBLP BibTeX RDF
15	Nadja Betzler, Robert Bredereck, Rolf Niedermeier, Johannes Uhlmann	On Bounded-Degree Vertex Deletion parameterized by treewidth.	Discret. Appl. Math.	2012	DBLP DOI BibTeX RDF
15	David Knipe	Trimming weighted graphs of bounded treewidth.	Discret. Appl. Math.	2012	DBLP DOI BibTeX RDF
15	Yong Gao 0001	Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs.	Discret. Appl. Math.	2012	DBLP DOI BibTeX RDF
15	Bireswar Das, Jacobo Torán, Fabian Wagner	Restricted space algorithms for isomorphism on bounded treewidth graphs.	Inf. Comput.	2012	DBLP DOI BibTeX RDF
15	Ondrej Kuzelka, Andrea Szabóová, Filip Zelezný	Reducing Examples in Relational Learning with Bounded-Treewidth Hypotheses.	NFMCP	2012	DBLP DOI BibTeX RDF
15	John Fearnley, Sven Schewe	Time and Parallelizability Results for Parity Games with Bounded Treewidth.	ICALP (2)	2012	DBLP DOI BibTeX RDF
15	Adrian Kosowski, Bi Li 0004, Nicolas Nisse, Karol Suchan	k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth.	ICALP (2)	2012	DBLP DOI BibTeX RDF
15	Hans L. Bodlaender	Fixed-Parameter Tractability of Treewidth and Pathwidth.	The Multivariate Algorithmic Revolution and Beyond	2012	DBLP DOI BibTeX RDF
15	Daniel Reidenbach, Markus L. Schmid	Patterns with Bounded Treewidth.	LATA	2012	DBLP DOI BibTeX RDF
15	Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani	h-Quasi Planar Drawings of Bounded Treewidth Graphs in Linear Area.	WG	2012	DBLP DOI BibTeX RDF
15	Dieter Mitsche, Guillem Perarnau	On the treewidth and related parameters of random geometric graphs.	STACS	2012	DBLP DOI BibTeX RDF
15	Ken-ichi Kawarabayashi, Yusuke Kobayashi 0001	Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid.	STACS	2012	DBLP DOI BibTeX RDF
15	Itamar Hartstein, Mordechai Shalom, Shmuel Zaks	On the Complexity of the Regenerator Location Problem - Treewidth and Other Parameters - (Extended Abstract).	WAOA	2012	DBLP DOI BibTeX RDF
15	Abhay Kumar Jha, Dan Suciu	On the tractability of query compilation and bounded treewidth.	ICDT	2012	DBLP DOI BibTeX RDF
15	Alexander Fix, Joyce Chen, Endre Boros, Ramin Zabih	Approximate MRF Inference Using Bounded Treewidth Subgraphs.	ECCV (1)	2012	DBLP DOI BibTeX RDF
15	Per Austrin, Toniann Pitassi, Yu Wu	Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems.	APPROX-RANDOM	2012	DBLP DOI BibTeX RDF
15	Pablo Barceló, Leonid Libkin, Miguel Romero 0001	On Low Treewidth Approximations of Conjunctive Queries.	AMW	2012	DBLP BibTeX RDF
15	Takashi Yamada, Takayoshi Shoudai	Efficient Pattern Matching on Graph Patterns of Bounded Treewidth.	Electron. Notes Discret. Math.	2011	DBLP DOI BibTeX RDF
15	Markus Bläser, Christian Hoffmann 0001	Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.	Algorithmica	2011	DBLP DOI BibTeX RDF
15	Igor L. Markov, Yaoyun Shi	Constant-Degree Graph Expansions that Preserve Treewidth.	Algorithmica	2011	DBLP DOI BibTeX RDF
15	Jirí Fiala 0001, Petr A. Golovach, Jan Kratochvíl	Parameterized complexity of coloring problems: Treewidth versus vertex cover.	Theor. Comput. Sci.	2011	DBLP DOI BibTeX RDF
15	MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Dániel Marx	Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth.	J. ACM	2011	DBLP DOI BibTeX RDF
15	Fabian Wagner	Graphs of Bounded Treewidth can be Canonized in AC1.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
15	Christoph Blume, H. J. Sander Bruggink, Martin Friedrich, Barbara König 0001	Treewidth, Pathwidth and Cospan Decompositions.	Electron. Commun. Eur. Assoc. Softw. Sci. Technol.	2011	DBLP DOI BibTeX RDF
15	Gwenaël Joret, David R. Wood	Nordhaus-Gaddum for Treewidth	CoRR	2011	DBLP BibTeX RDF
15	Michal Pilipczuk	Problems parameterized by treewidth tractable in single exponential time: a logical approach	CoRR	2011	DBLP BibTeX RDF
15	Navin Kashyap, Andrew Thangaraj	On the Treewidth of MDS and Reed-Muller Codes	CoRR	2011	DBLP BibTeX RDF
15	David R. Wood	Treewidth of Cartesian Products of Highly Connected Graphs	CoRR	2011	DBLP BibTeX RDF
15	Dániel Marx, Barry O'Sullivan, Igor Razgon	Finding small separators in linear time via treewidth reduction	CoRR	2011	DBLP BibTeX RDF
15	Per Austrin, Toniann Pitassi, Yu Wu	Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems	CoRR	2011	DBLP BibTeX RDF
15	Bernard Mans, Luke Mathieson	On the Treewidth of Dynamic Graphs	CoRR	2011	DBLP BibTeX RDF
15	Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk	Solving connectivity problems parameterized by treewidth in single exponential time	CoRR	2011	DBLP BibTeX RDF
15	Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak	An Efficient Partitioning Oracle for Bounded-Treewidth Graphs	CoRR	2011	DBLP BibTeX RDF
15	Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch	Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization	CoRR	2011	DBLP BibTeX RDF
15	Kitty Meeks, Alexander Scott 0001	The Parameterised Complexity of List Problems on Graphs of Bounded Treewidth	CoRR	2011	DBLP BibTeX RDF
15	Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman	Treewidth governs the complexity of target set selection.	Discret. Optim.	2011	DBLP DOI BibTeX RDF
15	Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh 0001, Stefan Szeider, Carsten Thomassen	On the complexity of some colorful problems parameterized by treewidth.	Inf. Comput.	2011	DBLP DOI BibTeX RDF
15	Hans L. Bodlaender, Arie M. C. A. Koster	Treewidth computations II. Lower bounds.	Inf. Comput.	2011	DBLP DOI BibTeX RDF
15	Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos	Contraction obstructions for treewidth.	J. Comb. Theory, Ser. B	2011	DBLP DOI BibTeX RDF
15	Fabien de Montgolfier, Mauricio Soto, Laurent Viennot	Treewidth and Hyperbolicity of the Internet.	NCA	2011	DBLP DOI BibTeX RDF
15	Daniel Lokshtanov, Dániel Marx, Saket Saurabh 0001	Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal.	SODA	2011	DBLP DOI BibTeX RDF
15	Alexander Hein, Arie M. C. A. Koster	An Experimental Evaluation of Treewidth at Most Four Reductions.	SEA	2011	DBLP DOI BibTeX RDF
15	Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk	Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.	FOCS	2011	DBLP DOI BibTeX RDF
15	Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch	Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization.	ICALP (1)	2011	DBLP DOI BibTeX RDF
15	Arash Farzan, Shahin Kamali	Compact Navigation and Distance Oracles for Graphs with Small Treewidth.	ICALP (1)	2011	DBLP DOI BibTeX RDF
15	Navin Kashyap, Andrew Thangaraj	On the treewidth of MDS and Reed-Muller codes.	ISIT	2011	DBLP DOI BibTeX RDF
15	Michal Pilipczuk	Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach.	MFCS	2011	DBLP DOI BibTeX RDF
15	Fabian Wagner	Graphs of Bounded Treewidth Can Be Canonized in AC1.	CSR	2011	DBLP DOI BibTeX RDF
15	Yang Yuan	A Fast Parallel Branch and Bound Algorithm for Treewidth.	ICTAI	2011	DBLP DOI BibTeX RDF
15	Markus Chimani, Petra Mutzel, Bernd Zey	Improved Steiner Tree Algorithms for Bounded Treewidth.	IWOCA	2011	DBLP DOI BibTeX RDF
15	Takashi Yamada, Takayoshi Shoudai	Graph Contraction Pattern Matching for Graphs of Bounded Treewidth.	ILP (Late Breaking Papers)	2011	DBLP DOI BibTeX RDF
15	Chaoyi Wang, Tian Liu 0001, Peng Cui 0008, Ke Xu 0001	A Note on Treewidth in Random Graphs.	COCOA	2011	DBLP DOI BibTeX RDF
15	Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak	An Efficient Partitioning Oracle for Bounded-Treewidth Graphs.	APPROX-RANDOM	2011	DBLP DOI BibTeX RDF
15	Léon Planken, Mathijs de Weerdt, Roman van der Krogt	Computing All-Pairs Shortest Paths by Leveraging Low Treewidth.	ICAPS	2011	DBLP BibTeX RDF
15	Manuel Bodirsky, Stefan Wölfl 0001	RCC8 Is Polynomial on Networks of Bounded Treewidth.	IJCAI	2011	DBLP DOI BibTeX RDF
15	Luca Pulina, Armando Tacchella	An Empirical Study of QBF Encodings: from Treewidth Estimation to Useful Preprocessing.	Fundam. Informaticae	2010	DBLP DOI BibTeX RDF
15	Georg Gottlob, Reinhard Pichler, Fang Wei 0001	Monadic datalog over finite structures of bounded treewidth.	ACM Trans. Comput. Log.	2010	DBLP DOI BibTeX RDF
15	Dániel Marx	Can You Beat Treewidth?	Theory Comput.	2010	DBLP DOI BibTeX RDF
15	Leizhen Cai, Yongxi Cheng, Elad Verbin, Yuan Zhou 0007	Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem.	SIAM J. Discret. Math.	2010	DBLP DOI BibTeX RDF
15	Georg Gottlob, Reinhard Pichler, Fang Wei 0001	Bounded treewidth as a key to tractability of knowledge representation and reasoning.	Artif. Intell.	2010	DBLP DOI BibTeX RDF
15	Eyal Amir	Approximation Algorithms for Treewidth.	Algorithmica	2010	DBLP DOI BibTeX RDF
15	Julia Böttcher, Klaas Paul Pruessmann, Anusch Taraz, Andreas Würfl	Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs.	Eur. J. Comb.	2010	DBLP DOI BibTeX RDF
15	Daniel Meister 0001	Treewidth and minimum fill-in on permutation graphs in linear time.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
15	Marko Samer, Stefan Szeider	Constraint satisfaction with bounded treewidth revisited.	J. Comput. Syst. Sci.	2010	DBLP DOI BibTeX RDF
15	Daniel Lokshtanov, Dániel Marx, Saket Saurabh 0001	Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal	CoRR	2010	DBLP BibTeX RDF
15	M. Praveen	Does Treewidth Help in Modal Satisfiability?	CoRR	2010	DBLP BibTeX RDF
15	Hermann Gruber	On Balanced Separators, Treewidth, and Cycle Rank	CoRR	2010	DBLP BibTeX RDF
15	Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra	Approximating Sparsest Cut in Graphs of Bounded Treewidth	CoRR	2010	DBLP BibTeX RDF
15	Bireswar Das, Jacobo Torán, Fabian Wagner	Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs	CoRR	2010	DBLP BibTeX RDF
15	Federico Mancini 0001	Minimum fill-in and treewidth of split+ke and split+kv graphs.	Discret. Appl. Math.	2010	DBLP DOI BibTeX RDF
15	Ana Silva 0001, Aline Alves da Silva, Cláudia Linhares Sales	A bound on the treewidth of planar even-hole-free graphs.	Discret. Appl. Math.	2010	DBLP DOI BibTeX RDF
15	Georg Gottlob, Reinhard Pichler, Fang Wei 0001	Tractable database design and datalog abduction through bounded treewidth.	Inf. Syst.	2010	DBLP DOI BibTeX RDF
15	Li Xianglu	Page Number and Graph Treewidth.	Int. J. Appl. Metaheuristic Comput.	2010	DBLP DOI BibTeX RDF
15	Hans L. Bodlaender, Arie M. C. A. Koster	Treewidth computations I. Upper bounds.	Inf. Comput.	2010	DBLP DOI BibTeX RDF
15	Reinhard Pichler, Stefan Rümmele, Stefan Woltran	Counting and Enumeration Problems with Bounded Treewidth.	LPAR (Dakar)	2010	DBLP DOI BibTeX RDF
15	Qiong Cheng, Piotr Berman, Robert W. Harrison, Alexander Zelikovsky	Efficient Alignments of Metabolic Networks with Bounded Treewidth.	ICDM Workshops	2010	DBLP DOI BibTeX RDF
15	Reinhard Pichler	Exploiting Bounded Treewidth with Datalog (A Survey).	Datalog	2010	DBLP DOI BibTeX RDF
15	Michael Lampis	Algorithmic Meta-theorems for Restrictions of Treewidth.	ESA (1)	2010	DBLP DOI BibTeX RDF
15	M. Praveen	Does Treewidth Help in Modal Satisfiability? - (Extended Abstract).	MFCS	2010	DBLP DOI BibTeX RDF
15	Jing He 0009, Hongyu Liang, Jayalal Sarma	Limiting Negations in Bounded Treewidth and Upward Planar Circuits.	MFCS	2010	DBLP DOI BibTeX RDF
15	Maurice J. Jansen, Jayalal Sarma	Balancing Bounded Treewidth Circuits.	CSR	2010	DBLP DOI BibTeX RDF
15	Johan Kwisthout, Hans L. Bodlaender, Linda C. van der Gaag	The Necessity of Bounded Treewidth for Efficient Inference in Bayesian Networks.	ECAI	2010	DBLP BibTeX RDF
15	Dániel Marx, Barry O'Sullivan, Igor Razgon	Treewidth Reduction for Constrained Separation and Bipartization Problems.	STACS	2010	DBLP DOI BibTeX RDF
15	Bireswar Das, Jacobo Torán, Fabian Wagner	Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs.	STACS	2010	DBLP DOI BibTeX RDF
15	Reinhard Pichler, Stefan Rümmele, Stefan Szeider, Stefan Woltran	Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth Is not Enough.	KR	2010	DBLP BibTeX RDF
15	Michael J. Dinneen, Masoud Khosravani	A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs.	SIROCCO	2010	DBLP DOI BibTeX RDF
15	Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra	Approximating Sparsest Cut in Graphs of Bounded Treewidth.	APPROX-RANDOM	2010	DBLP DOI BibTeX RDF
15	Sergio Cabello, Christian Knauer	Algorithms for graphs of bounded treewidth via orthogonal range searching.	Comput. Geom.	2009	DBLP DOI BibTeX RDF
15	Selma Djelloul	Treewidth and logical definability of graph products.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF
15	Bireswar Das, Jacobo Torán, Fabian Wagner	Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs.	Electron. Colloquium Comput. Complex.	2009	DBLP BibTeX RDF
15	Dániel Marx, Barry O'Sullivan, Igor Razgon	Treewidth reduction for constrained separation and bipartization problems	CoRR	2009	DBLP BibTeX RDF
15	MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx	Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth	CoRR	2009	DBLP BibTeX RDF
15	Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann	The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs	CoRR	2009	DBLP BibTeX RDF
15	Markus Bläser, Christian Hoffmann 0001	Fast computation of interlace polynomials on graphs of bounded treewidth	CoRR	2009	DBLP BibTeX RDF
15	Yong Gao 0001	Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free Random Graphs	CoRR	2009	DBLP BibTeX RDF
15	Maurice J. Jansen, Jayalal Sarma	Balancing Bounded Treewidth Circuits	CoRR	2009	DBLP BibTeX RDF
15	Frederic Dorn, Jan Arne Telle	Semi-nice tree-decompositions: The best of branchwidth, treewidth and pathwidth with one algorithm.	Discret. Appl. Math.	2009	DBLP DOI BibTeX RDF
15	Michael J. Pelsmajer	Equitable list coloring and treewidth.	J. Graph Theory	2009	DBLP DOI BibTeX RDF