Search results for "Treewidth"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
152	Andrea Ferrara, Guoqiang Pan, Moshe Y. Vardi	Treewidth in Verification: Local vs. Global.	LPAR	2005	DBLP DOI BibTeX RDF
120	Pierre Fraigniaud, Nicolas Nisse	Connected Treewidth and Connected Graph Searching.	LATIN	2006	DBLP DOI BibTeX RDF
103	Erik D. Demaine, Mohammad Taghi Hajiaghayi	Equivalence of local treewidth and linear local treewidth and its algorithmic applications.	SODA	2004	DBLP BibTeX RDF
99	Víctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi	Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics.	CP	2002	DBLP DOI BibTeX RDF
89	Jens Gustedt, Ole A. Mæhle, Jan Arne Telle	The Treewidth of Java Programs.	ALENEX	2002	DBLP DOI BibTeX RDF
89	Derek G. Corneil, Udi Rotics	On the Relationship between Clique-Width and Treewidth.	WG	2001	DBLP DOI BibTeX RDF
89	Ton Kloks, Hans L. Bodlaender	Approximating Treewidth and Pathwidth of some Classes of Perfect Graphs.	ISAAC	1992	DBLP DOI BibTeX RDF
86	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
86	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
78	Yuliya Zabiyaka, Adnan Darwiche	Functional Treewidth: Bounding Complexity in the Presence of Functional Dependencies.	SAT	2006	DBLP DOI BibTeX RDF
78	Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos	Bidimensional Parameters and Local Treewidth.	LATIN	2004	DBLP DOI BibTeX RDF
76	Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse	Nondeterministic Graph Searching: From Pathwidth to Treewidth.	MFCS	2005	DBLP DOI BibTeX RDF	treewidth, graph searching, pathwidth
76	Hans L. Bodlaender, Udi Rotics	Computing the Treewidth and the Minimum Fill-in with the Modular Decomposition.	SWAT	2002	DBLP DOI BibTeX RDF	minimum fill-in, minimal separators, graph algorithms, treewidth, Algorithms and data structures, modular decomposition
67	Marko Samer, Helmut Veith	Encoding Treewidth into SAT.	SAT	2009	DBLP DOI BibTeX RDF
67	Emgad H. Bachoore, Hans L. Bodlaender	Weighted Treewidth Algorithmic Techniques and Results.	ISAAC	2007	DBLP DOI BibTeX RDF
67	Dániel Marx	Can you beat treewidth?	FOCS	2007	DBLP DOI BibTeX RDF
67	Fedor V. Fomin, Dimitrios M. Thilikos	Dominating Sets and Local Treewidth.	ESA	2003	DBLP DOI BibTeX RDF
67	Yong Gao 0001, Joseph C. Culberson	On the Treewidth of NK Landscapes.	GECCO	2003	DBLP DOI BibTeX RDF
67	Hans L. Bodlaender	On Reduction Algorithms for Graphs with Small Treewidth.	WG	1993	DBLP DOI BibTeX RDF
67	Hans L. Bodlaender	NC-Algorithms for Graphs with Small Treewidth.	WG	1988	DBLP DOI BibTeX RDF
65	Fedor V. Fomin, Serge Gaspers, Saket Saurabh 0001, 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
65	Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse	Nondeterministic Graph Searching: From Pathwidth to Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Treewidth, Graph searching, Pathwidth
65	Georg Gottlob, Stephanie Tien Lee, Gregory Valiant	Size and treewidth bounds for conjunctive queries.	PODS	2009	DBLP DOI BibTeX RDF	size bounds, database theory, conjunctive queries, treewidth
65	Hans L. Bodlaender, Alexander Grigoriev, Arie M. C. A. Koster	Treewidth Lower Bounds with Brambles.	Algorithmica	2008	DBLP DOI BibTeX RDF	Bramble, Grid minor, Approximation algorithm, Lower bound, Planar graph, Treewidth
65	Georg Gottlob, Reinhard Pichler, Fang Wei 0001	Tractable database design through bounded treewidth.	PODS	2006	DBLP DOI BibTeX RDF	database design, normal forms, fixed-parameter tractability, tree decomposition, bounded treewidth
65	Hans L. Bodlaender, Udi Rotics	Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition.	Algorithmica	2003	DBLP DOI BibTeX RDF	Minimum fill-in, Minimal separators, Graph algorithms, Treewidth, Polynomial algorithms, Modular decomposition
63	Hans L. Bodlaender, Joost Engelfriet	Domino Treewith (Extended Abstract).	WG	1994	DBLP DOI BibTeX RDF
61	Hans L. Bodlaender	Necessary Edges in k-Chordalisations of Graphs.	J. Comb. Optim.	2003	DBLP DOI BibTeX RDF	triangulated graphs, graph algorithms, interval graphs, treewidth, chordal graphs, pathwidth
61	Koichi Yamazaki, Hans L. Bodlaender, Babette de Fluiter, Dimitrios M. Thilikos	Isomorphism for Graphs of Bounded Distance Width.	Algorithmica	1999	DBLP DOI BibTeX RDF	Distance pathwidth, Distance treewidth, Graph isomorphism, Fixed parameter tractability
60	Dániel Marx	Four Shorts Stories on Surprising Algorithmic Uses of Treewidth.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
60	Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, Philipp Zschoche	As Time Goes By: Reflections on Treewidth for Temporal Graphs.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
60	Tom C. van der Zanden	Games, Puzzles and Treewidth.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
60	Hisao Tamaki	Experimental Analysis of Treewidth.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
60	Alexander Grigoriev	Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
60	Marcin Pilipczuk	Surprising Applications of Treewidth Bounds for Planar Graphs.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
57	Erik D. Demaine, MohammadTaghi Hajiaghayi	Linearity of grid minors in treewidth with applications through bidimensionality.	Comb.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 05C83, 68R10, 05C85
57	Frank van den Eijkhof, Hans L. Bodlaender, Arie M. C. A. Koster	Safe Reduction Rules for Weighted Treewidth.	Algorithmica	2007	DBLP DOI BibTeX RDF
57	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
57	Marko Samer, Stefan Szeider	Constraint Satisfaction with Bounded Treewidth Revisited.	CP	2006	DBLP DOI BibTeX RDF
57	Erik D. Demaine, Mohammad Taghi Hajiaghayi	Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality.	SODA	2005	DBLP BibTeX RDF
57	Arie M. C. A. Koster, Thomas Wolle, Hans L. Bodlaender	Degree-Based Treewidth Lower Bounds.	WEA	2005	DBLP DOI BibTeX RDF
57	Hans L. Bodlaender, Alexander Grigoriev, Arie M. C. A. Koster	Treewidth Lower Bounds with Brambles.	ESA	2005	DBLP DOI BibTeX RDF
57	François Clautiaux, Jacques Carlier, Aziz Moukrim, Stéphane Nègre	New Lower and Upper Bounds for Graph Treewidth.	WEA	2003	DBLP DOI BibTeX RDF
57	Frank van den Eijkhof, Hans L. Bodlaender	Safe Reduction Rules for Weighted Treewidth.	WG	2002	DBLP DOI BibTeX RDF
57	Hans L. Bodlaender, Richard B. Tan, Dimitrios M. Thilikos, Jan van Leeuwen	On Interval Routing Schemes and Treewidth.	WG	1995	DBLP DOI BibTeX RDF
57	Hans L. Bodlaender, Ton Kloks, Dieter Kratsch	Treewidth and Pathwidth of Permutation Graphs.	ICALP	1993	DBLP DOI BibTeX RDF
55	Georg Gottlob, Reinhard Pichler, Fang Wei 0001	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
55	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.	COCOA	2007	DBLP DOI BibTeX RDF	Topics Parameterized Complexity, Graph Coloring, Bounded Treewidth
55	Erik D. Demaine, Mohammad Taghi Hajiaghayi	Diameter and Treewidth in Minor-Closed Graph Families, Revisited.	Algorithmica	2004	DBLP DOI BibTeX RDF	Apex graphs, Bounded local treewidth, Approximation algorithms, Graph algorithms, Graph minors
53	Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh 0001	Clique-width: on the price of generality.	SODA	2009	DBLP DOI BibTeX RDF
53	Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman	An exact almost optimal algorithm for target set selection in social networks.	EC	2009	DBLP DOI BibTeX RDF	bounded tree-width algorithm, bounded tree-width lower-bound, target set selection, social networks, viral marketing
53	Guoqiang Pan, Moshe Y. Vardi	Fixed-Parameter Hierarchies inside PSPACE.	LICS	2006	DBLP DOI BibTeX RDF
51	Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee	Improved approximation algorithms for minimum-weight vertex separators.	STOC	2005	DBLP DOI BibTeX RDF	vertex separators, approximation algorithms, semidefinite programming, treewidth, metric embeddings
51	Hans L. Bodlaender	Polynomial Algorithms for Graph Isomorphism and Chromatic Index on Partial k-Trees.	SWAT	1988	DBLP DOI BibTeX RDF	Chromatic Index, graphs with small treewidth, polynomial time algorithms, NP-complete problems, Graph Isomorphism, tree-decompositions, partial k-trees
46	Luca Pulina, Armando Tacchella	Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic Encodings.	LPAR	2008	DBLP DOI BibTeX RDF
46	K. Nunez, Jianhua Chen 0003, Peter P. Chen, Guoli Ding, Robert F. Lax, Brian D. Marx	Empirical Comparison of Greedy Strategies for Learning Markov Networks of Treewidth k.	ICMLA	2008	DBLP DOI BibTeX RDF
46	Vida Dujmovic, David R. Wood	Graph Treewidth and Geometric Thickness Parameters.	Discret. Comput. Geom.	2007	DBLP DOI BibTeX RDF
46	Federico Mancini 0001	Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs.	ISAAC	2007	DBLP DOI BibTeX RDF
46	Jirí Fiala 0001, Petr A. Golovach, Jan Kratochvíl	Distance Constrained Labelings of Graphs of Bounded Treewidth.	ICALP	2005	DBLP DOI BibTeX RDF
46	Hans L. Bodlaender, Arie M. C. A. Koster, Thomas Wolle	Contraction and Treewidth Lower Bounds.	ESA	2004	DBLP DOI BibTeX RDF
46	Thomas Wolle	A Framework for Network Reliability Problems on Graphs of Bounded Treewidth.	ISAAC	2002	DBLP DOI BibTeX RDF
46	Mohammad Taghi Hajiaghayi, Naomi Nishimura	Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth.	MFCS	2002	DBLP DOI BibTeX RDF
46	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos	-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor.	APPROX	2002	DBLP DOI BibTeX RDF
46	Volker Heun, Ernst W. Mayr	Embedding Graphs with Bounded Treewidth into Optimal Hypercubes.	STACS	1996	DBLP DOI BibTeX RDF
46	Shiva Chaudhuri, Christos D. Zaroliagis	Optimal Parallel Shortest Paths in Small Treewidth Digraphs.	ESA	1995	DBLP DOI BibTeX RDF
46	Hans L. Bodlaender, Torben Hagerup	Parallel Algorithms with Optimal Speedup for Bounded Treewidth.	ICALP	1995	DBLP DOI BibTeX RDF
46	Siddharthan Ramachandramurthi	A Lower Bound for Treewidth and Its Consequences.	WG	1994	DBLP DOI BibTeX RDF
46	Ton Kloks	Treewidth of Circle Graphs.	ISAAC	1993	DBLP DOI BibTeX RDF
46	Hans L. Bodlaender, Ton Kloks	Better Algorithms for the Pathwidth and Treewidth of Graphs.	ICALP	1991	DBLP DOI BibTeX RDF
45	Fedor V. Fomin, Stefan Kratsch, Erik Jan van Leeuwen (eds.)	Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Danny Hermelin	Hans Bodlaender and the Theory of Kernelization Lower Bounds.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Michal Pilipczuk	Computing Tree Decompositions.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Jan van Leeuwen	Algorithms, Complexity, and Hans.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Jesper Nederlof	Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Yota Otachi	A Survey on Spanning Tree Congestion.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Bart M. P. Jansen	Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Daniel Lokshtanov, Saket Saurabh 0001, Meirav Zehavi	Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Stefan Arnborg, Andrzej Proskurowski	Seeing Arboretum for the (partial k-) Trees.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Dimitrios M. Thilikos	A Retrospective on (Meta) Kernelization.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Mark de Berg, Sándor Kisfaludi-Bak	Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Johan M. M. van Rooij	Fast Algorithms for Join Operations on Tree Decompositions.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
45	Michael R. Fellows, Frances A. Rosamond	Collaborating with Hans: Some Remaining Wonderments.	Treewidth, Kernels, and Algorithms	2020	DBLP DOI BibTeX RDF
44	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	A Note on Multiflows and Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Product multicommodity flow, Treewidth, Edge-disjoint paths
44	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
44	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
42	Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, Saket Saurabh 0001	Graph Layout Problems Parameterized by Vertex Cover.	ISAAC	2008	DBLP DOI BibTeX RDF
42	Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach	Spanners in Sparse Graphs.	ICALP (1)	2008	DBLP DOI BibTeX RDF
42	Daniele Pretolani	Hypergraph Reductions and Satisfiability Problems.	SAT	2003	DBLP DOI BibTeX RDF
42	David R. Karger, Nathan Srebro	Learning Markov networks: maximum bounded tree-width graphs.	SODA	2001	DBLP BibTeX RDF
40	Jiong Guo, Rolf Niedermeier, Daniel Raible 0001	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
40	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
40	Pierre Fraigniaud, Nicolas Nisse	Monotony Properties of Connected Visible Graph Searching.	WG	2006	DBLP DOI BibTeX RDF	Treewidth, Graph Searching, Pathwidth
40	Guillaume Fertin, André Raspaud, Bruce A. Reed	On Star Coloring of Graphs.	WG	2001	DBLP DOI BibTeX RDF	proper coloring, star coloring, acyclic coloring, graphs, treewidth, vertex coloring
36	Tamás Horváth 0001, Jan Ramon	Efficient Frequent Connected Subgraph Mining in Graphs of Bounded Treewidth.	ECML/PKDD (1)	2008	DBLP DOI BibTeX RDF
36	Michael Jakl, Reinhard Pichler, Stefan Rümmele, Stefan Woltran	Fast Counting with Bounded Treewidth.	LPAR	2008	DBLP DOI BibTeX RDF
36	Fedor V. Fomin, Yngve Villanger	Treewidth Computation and Extremal Combinatorics.	ICALP (1)	2008	DBLP DOI BibTeX RDF
36	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
36	Hans L. Bodlaender	Treewidth: Characterizations, Applications, and Computations.	WG	2006	DBLP DOI BibTeX RDF
36	Yngve Villanger	Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In.	LATIN	2006	DBLP DOI BibTeX RDF
36	Emgad H. Bachoore, Hans L. Bodlaender	A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth.	AAIM	2006	DBLP DOI BibTeX RDF