Search results for "Bounded treewidth"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx	Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth.	STOC	2010	DBLP DOI BibTeX RDF	Steiner forest, bounded-genus graphs, bounded-treewidth graphs, planar graphs, PTAS, series-parallel graphs
3	Elisabeth Gassner, Johannes Hatzl	A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs.	Computing	2008	DBLP DOI BibTeX RDF	Neighbourhood domination, Parity constraints, Distance-hereditary graphs, Bounded treewidth
3	Georg Gottlob, Reinhard Pichler, Fang Wei	Tractable database design through bounded treewidth.	PODS	2006	DBLP DOI BibTeX RDF	database design, normal forms, fixed-parameter tractability, tree decomposition, bounded treewidth
2	Anil Maheshwari, Norbert Zeh	I/O-Efficient Algorithms for Graphs of Bounded Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Algorithms, Graph algorithms, External memory algorithms, Bounded treewidth
2	Michael R. Fellows, Danny Hermelin, Frances A. Rosamond	Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs.	IWPEC	2009	DBLP DOI BibTeX RDF
2	Tamás Horváth, Jan Ramon	Efficient Frequent Connected Subgraph Mining in Graphs of Bounded Treewidth.	ECML/PKDD	2008	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender, Alexander Grigoriev, Nadejda V. Grigorieva, Albert Hendriks	The Valve Location Problem in Simple Network Topologies.	WG	2008	DBLP DOI BibTeX RDF	Valve location problem, computational complexity, dynamic programming, binary search, bounded treewidth
2	Jiong Guo, Rolf Niedermeier, Daniel Raible	Improved Algorithms and Complexity Results for Power Domination in Graphs.	Algorithmica	2008	DBLP DOI BibTeX RDF	Graphs of bounded treewidth, (Power) domination in graphs, Computational complexity, Graph algorithms, Parameterized complexity, Design and analysis of algorithms, Fixed-parameter algorithms
2	Tong Yi, Guoli Ding, Bogdan Oporowski	A Low Bound for Broadcast in Optical Networks of Bounded Treewidth Using Fewest Converters.	IPCCC	2007	DBLP DOI BibTeX RDF
2	Uffe Flarup, Pascal Koiran, Laurent Lyaudet	On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices.	ISAAC	2007	DBLP DOI BibTeX RDF
2	Georg Gottlob, Reinhard Pichler, Fang Wei	Monadic datalog over finite structures with bounded treewidth.	PODS	2007	DBLP DOI BibTeX RDF	datalog, treewidth, fixed-parameter tractability, monadic second order logic, tree decomposition
2	Hans L. Bodlaender, Fedor V. Fomin	Equitable Colorings of Bounded Treewidth Graphs.	MFCS	2004	DBLP DOI BibTeX RDF
2	Mohammad Taghi Hajiaghayi, Naomi Nishimura	Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth.	MFCS	2002	DBLP DOI BibTeX RDF
2	Thomas Wolle	A Framework for Network Reliability Problems on Graphs of Bounded Treewidth.	ISAAC	2002	DBLP DOI BibTeX RDF
2	Víctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi	Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics.	CP	2002	DBLP BibTeX RDF
2	Anil Maheshwari, Norbert Zeh	I/O-efficient algorithms for graphs of bounded treewidth.	SODA	2001	DBLP DOI BibTeX RDF
2	Torben Hagerup	Dynamic Algorithms for Graphs of Bounded Treewidth.	Algorithmica	2000	DBLP DOI BibTeX RDF
2	Torben Hagerup	Dynamic Algorithms for Graphs of Bounded Treewidth.	ICALP	1997	DBLP DOI BibTeX RDF
2	Volker Heun, Ernst W. Mayr	Embedding Graphs with Bounded Treewidth into Optimal Hypercubes.	STACS	1996	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender, Torben Hagerup	Parallel Algorithms with Optimal Speedup for Bounded Treewidth.	ICALP	1995	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender	Dynamic Programming on Graphs with Bounded Treewidth.	ICALP	1988	DBLP DOI BibTeX RDF	graph decision problems, restrictions of NP-complete problems, local condition compositions, dynamic programming, polynomial time algorithms, Treewidth, partial k-trees
1	Michael R. Fellows, Danny Hermelin, Frances A. Rosamond	Well Quasi Orders in Subclasses of Bounded Treewidth Graphs and Their Algorithmic Applications.	Algorithmica	2012	DBLP DOI BibTeX RDF
1	Parinya Chalermsook, Shiva Kintali, Richard J. Lipton, Danupon Nanongkai	Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs	CoRR	2012	DBLP BibTeX RDF
1	Serge Gaspers, Stefan Szeider	Strong Backdoors to Bounded Treewidth SAT	CoRR	2012	DBLP BibTeX RDF
1	Reinhard Pichler, Stefan Rümmele, Stefan Szeider, Stefan Woltran	Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough	CoRR	2012	DBLP BibTeX RDF
1	David Knipe	Trimming weighted graphs of bounded treewidth.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Daniel Reidenbach, Markus L. Schmid	Patterns with Bounded Treewidth.	LATA	2012	DBLP DOI BibTeX RDF
1	Takashi Yamada, Takayoshi Shoudai	Efficient Pattern Matching on Graph Patterns of Bounded Treewidth.	Electronic Notes in Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Fabian Wagner	Graphs of Bounded Treewidth can be Canonized in AC1.	Electronic Colloquium on Computational Complexity (ECCC)	2011	DBLP BibTeX RDF
1	Markus Bläser, Christian Hoffmann	Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.	Algorithmica	2011	DBLP DOI BibTeX RDF
1	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
1	Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak	An Efficient Partitioning Oracle for Bounded-Treewidth Graphs	CoRR	2011	DBLP BibTeX RDF
1	John Fearnley, Sven Schewe	Time and Space Results for Parity Games with Bounded Treewidth	CoRR	2011	DBLP BibTeX RDF
1	Kitty Meeks, Alexander Scott	The Parameterised Complexity of List Problems on Graphs of Bounded Treewidth	CoRR	2011	DBLP BibTeX RDF
1	Fabian Wagner	Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$\mbox{{\sf AC}.	CSR	2011	DBLP DOI BibTeX RDF
1	Daniel Lokshtanov, Dániel Marx, Saket Saurabh	Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal.	SODA	2011	DBLP BibTeX RDF
1	Manuel Bodirsky, Stefan Wölfl	RCC8 Is Polynomial on Networks of Bounded Treewidth.	IJCAI	2011	DBLP BibTeX RDF
1	Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak	An Efficient Partitioning Oracle for Bounded-Treewidth Graphs.	APPROX-RANDOM	2011	DBLP DOI BibTeX RDF
1	Markus Chimani, Petra Mutzel, Bernd Zey	Improved Steiner Tree Algorithms for Bounded Treewidth.	IWOCA	2011	DBLP DOI BibTeX RDF
1	Bireswar Das, Jacobo Torán, Fabian Wagner	Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs	CoRR	2010	DBLP BibTeX RDF
1	Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra	Approximating Sparsest Cut in Graphs of Bounded Treewidth	CoRR	2010	DBLP BibTeX RDF
1	Daniel Lokshtanov, Dániel Marx, Saket Saurabh	Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal	CoRR	2010	DBLP BibTeX RDF
1	Georg Gottlob, Reinhard Pichler, Fang Wei	Tractable database design and datalog abduction through bounded treewidth.	Inf. Syst.	2010	DBLP DOI BibTeX RDF
1	Leizhen Cai, Yongxi Cheng, Elad Verbin, Yuan Zhou	Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem.	SIAM J. Discrete Math.	2010	DBLP DOI BibTeX RDF
1	Georg Gottlob, Reinhard Pichler, Fang Wei	Bounded treewidth as a key to tractability of knowledge representation and reasoning.	Artif. Intell.	2010	DBLP DOI BibTeX RDF
1	Marko Samer, Stefan Szeider	Constraint satisfaction with bounded treewidth revisited.	J. Comput. Syst. Sci.	2010	DBLP DOI BibTeX RDF
1	Georg Gottlob, Reinhard Pichler, Fang Wei	Monadic datalog over finite structures of bounded treewidth.	ACM Trans. Comput. Log.	2010	DBLP DOI BibTeX RDF
1	Maurice J. Jansen, Jayalal M. N. Sarma	Balancing Bounded Treewidth Circuits.	CSR	2010	DBLP DOI BibTeX RDF
1	Qiong Cheng, Piotr Berman, Robert W. Harrison, Alexander Zelikovsky	Efficient Alignments of Metabolic Networks with Bounded Treewidth.	ICDM Workshops	2010	DBLP DOI BibTeX RDF
1	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
1	Reinhard Pichler, Stefan Rümmele, Stefan Woltran	Counting and Enumeration Problems with Bounded Treewidth.	LPAR (Dakar)	2010	DBLP DOI BibTeX RDF
1	Jing He, Hongyu Liang, Jayalal M. N. Sarma	Limiting Negations in Bounded Treewidth and Upward Planar Circuits.	MFCS	2010	DBLP DOI BibTeX RDF
1	Bireswar Das, Jacobo Torán, Fabian Wagner	Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs.	STACS	2010	DBLP DOI BibTeX RDF
1	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
1	Reinhard Pichler	Exploiting Bounded Treewidth with Datalog (A Survey).	Datalog	2010	DBLP DOI BibTeX RDF
1	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
1	Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra	Approximating Sparsest Cut in Graphs of Bounded Treewidth.	APPROX-RANDOM	2010	DBLP DOI BibTeX RDF
1	Sergio Cabello, Éric Colin de Verdière, Francis Lazarus	Finding shortest non-trivial cycles in directed graphs on surfaces.	Symposium on Computational Geometry	2010	DBLP DOI BibTeX RDF	embedded graph, non-contractible cycle, non-separating cycle, directed graph, surface, computational topology, topological graph theory
1	Bireswar Das, Jacobo Torán, Fabian Wagner	Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs.	Electronic Colloquium on Computational Complexity (ECCC)	2009	DBLP BibTeX RDF
1	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
1	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
1	Maurice J. Jansen, Jayalal M. N. Sarma	Balancing Bounded Treewidth Circuits	CoRR	2009	DBLP BibTeX RDF
1	Markus Bläser, Christian Hoffmann	Fast computation of interlace polynomials on graphs of bounded treewidth	CoRR	2009	DBLP BibTeX RDF
1	Sergio Cabello, Christian Knauer	Algorithms for graphs of bounded treewidth via orthogonal range searching.	Comput. Geom.	2009	DBLP DOI BibTeX RDF
1	Markus Bläser, Christian Hoffmann	Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.	ESA	2009	DBLP DOI BibTeX RDF
1	Michael Jakl, Reinhard Pichler, Stefan Woltran	Answer-Set Programming with Bounded Treewidth.	IJCAI	2009	DBLP BibTeX RDF
1	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.	WINE	2009	DBLP DOI BibTeX RDF
1	Reinhard Pichler, Stefan Rümmele, Stefan Woltran	Belief Revision with Bounded Treewidth.	LPNMR	2009	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh	Clique-width: on the price of generality.	SODA	2009	DBLP DOI BibTeX RDF
1	Ken-ichi Kawarabayashi, Erik D. Demaine, MohammadTaghi Hajiaghayi	Additive approximation algorithms for list-coloring minor-closed class of graphs.	SODA	2009	DBLP DOI BibTeX RDF
1	Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani	Power Indices in Spanning Connectivity Games.	AAIM	2009	DBLP DOI BibTeX RDF	Banzhaf index, Shapley-Shubik index, Network connectivity, coalitional games
1	Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi	Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs.	ICALP	2009	DBLP DOI BibTeX RDF
1	Cristina Bazgan, Basile Couëtoux, Zsolt Tuza	Covering a Graph with a Constrained Forest (Extended Abstract).	ISAAC	2009	DBLP DOI BibTeX RDF
1	Mira Gonen, Yuval Shavitt	Approximating the Number of Network Motifs.	WAW	2009	DBLP DOI BibTeX RDF
1	Frank Kammer, Torsten Tholey	The k-Disjoint Paths Problem on Chordal Graphs.	WG	2009	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Alexey A. Stepanov	On Two Techniques of Combining Branching and Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Exact exponential time algorithms, #3-Coloring, #Minimum dominating set, Minimum maximal matching, k-Weighted vertex cover, NP hard problems, Treewidth, Parameterized algorithms
1	Marko Samer, Stefan Szeider	Backdoor Sets of Quantified Boolean Formulas.	J. Autom. Reasoning	2009	DBLP DOI BibTeX RDF	Backdoor sets, Variable dependencies, Parameterized complexity, Quantified Boolean formulas
1	Aline Alves da Silva, Ana Silva, Cláudia Linhares Sales	Even-hole-free planar graphs have bounded treewidth.	Electronic Notes in Discrete Mathematics	2008	DBLP DOI BibTeX RDF
1	Jiong Guo, Falk Hüffner, Erhan Kenar, Rolf Niedermeier, Johannes Uhlmann	Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs.	European Journal of Operational Research	2008	DBLP DOI BibTeX RDF
1	Hans L. Bodlaender, Arie M. C. A. Koster	Combinatorial Optimization on Graphs of Bounded Treewidth.	Comput. J.	2008	DBLP DOI BibTeX RDF
1	Georg Gottlob, Reinhard Pichler, Fang Wei	Monadic Datalog over Finite Structures with Bounded Treewidth	CoRR	2008	DBLP BibTeX RDF
1	Michael Jakl, Reinhard Pichler, Stefan Rümmele, Stefan Woltran	Fast Counting with Bounded Treewidth.	LPAR	2008	DBLP DOI BibTeX RDF
1	Georg Gottlob, Reinhard Pichler, Fang Wei	Abduction with Bounded Treewidth: From Theoretical Tractability to Practically Efficient Computation.	AAAI	2008	DBLP BibTeX RDF
1	Gal Elidan, Stephen Gould	Learning Bounded Treewidth Bayesian Networks.	NIPS	2008	DBLP BibTeX RDF
1	Ronald Koch, Martin Skutella, Ines Spenke	Maximum k -Splittable s , t -Flows.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	k-Splittable, s, t-Flow, Polynomial time approximation scheme, Bounded treewidth
1	Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent	Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums.	FOCS	2008	DBLP DOI BibTeX RDF
1	Uffe Flarup, Laurent Lyaudet	On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract).	CSR	2008	DBLP DOI BibTeX RDF
1	Johannes Köbler, Oleg Verbitsky	From Invariants to Canonization in Parallel.	CSR	2008	DBLP DOI BibTeX RDF
1	Andrei A. Bulatov, Andrei A. Krokhin, Benoit Larose	Dualities for Constraint Satisfaction Problems.	Complexity of Constraints	2008	DBLP DOI BibTeX RDF
1	Hermann Gruber, Markus Holzer	Provably Shorter Regular Expressions from Deterministic Finite Automata.	Developments in Language Theory	2008	DBLP DOI BibTeX RDF
1	Reinhard Pichler, Axel Polleres, Fang Wei, Stefan Woltran	dRDF: Entailment for Domain-Restricted RDF.	ESWC	2008	DBLP DOI BibTeX RDF
1	Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach	Spanners in Sparse Graphs.	ICALP	2008	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl	On tractability of Cops and Robbers game.	IFIP TCS	2008	DBLP DOI BibTeX RDF	Pursuit-evasion games on graphs, cliquewidth, algorithms, complexity, parameterized complexity
1	Frank Kammer, Torsten Tholey	The Complexity of Minimum Convex Coloring.	ISAAC	2008	DBLP DOI BibTeX RDF	Convex Coloring, Maximum Disjoint Paths Problem
1	Christian Wulff-Nilsen	Computing the Maximum Detour of a Plane Graph in Subquadratic Time.	ISAAC	2008	DBLP DOI BibTeX RDF
1	Stefan Szeider	Monadic Second Order Logic on Graphs with Local Cardinality Constraints.	MFCS	2008	DBLP DOI BibTeX RDF
1	Hans L. Bodlaender, Richard B. Tan, Thomas C. van Dijk, Jan van Leeuwen	Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint.	SWAT	2008	DBLP DOI BibTeX RDF
1	Adrian Kosowski, Alfredo Navarra, Maria Cristina Pinotti	Connectivity in Multi-interface Networks.	TGC	2008	DBLP DOI BibTeX RDF	multi-interface network, approximation algorithm, wireless network, Energy saving
1	David Coudert, Florian Huc, Dorian Mazauric	A Distributed Algorithm for Computing and Updating the Process Number of a Forest.	DISC	2008	DBLP DOI BibTeX RDF
1	Yuri Rabinovich	On Average Distortion of Embedding Metrics into the Line.	Discrete & Computational Geometry	2008	DBLP DOI BibTeX RDF	Average distortion, Metric embeddings