Search results for "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	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
3	Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse	Nondeterministic Graph Searching: From Pathwidth to Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Treewidth, Graph searching, Pathwidth
3	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
3	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
3	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
3	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
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	Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, 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
3	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
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
3	Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse	Nondeterministic Graph Searching: From Pathwidth to Treewidth.	MFCS	2005	DBLP DOI BibTeX RDF	treewidth, graph searching, pathwidth
3	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
3	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
3	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
3	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
2	Jirí Fiala, Petr A. Golovach, Jan Kratochvíl	Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover.	TAMC	2009	DBLP DOI BibTeX RDF
2	Marko Samer, Helmut Veith	Encoding Treewidth into SAT.	SAT	2009	DBLP DOI BibTeX RDF
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	Reinhard Pichler, Stefan Rümmele, Stefan Woltran	Belief Revision with Bounded Treewidth.	LPNMR	2009	DBLP DOI BibTeX RDF
2	Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi	Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction.	Algorithmica	2009	DBLP DOI BibTeX RDF	Bidimensionality, Wagner’s conjecture, Graph algorithms, Treewidth, Graph minors, Grid graphs
2	Erik D. Demaine, MohammadTaghi Hajiaghayi	Linearity of grid minors in treewidth with applications through bidimensionality.	Combinatorica	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 05C83, 68R10, 05C85
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	Luca Pulina, Armando Tacchella	Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic Encodings.	LPAR	2008	DBLP DOI BibTeX RDF
2	Michael Jakl, Reinhard Pichler, Stefan Rümmele, Stefan Woltran	Fast Counting with Bounded Treewidth.	LPAR	2008	DBLP DOI BibTeX RDF
2	Fedor V. Fomin, Yngve Villanger	Treewidth Computation and Extremal Combinatorics.	ICALP	2008	DBLP DOI BibTeX RDF
2	K. Nunez, Jianhua Chen, 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
2	Zhe Nie, Yueping Li, Xiaohong Zhou	Optimal Path Cover for Graphs of Small Treewidth.	NCM	2008	DBLP DOI BibTeX RDF	route design, algorithm, treewidth, path cover
2	Richard B. Borie, R. Gary Parker, Craig A. Tovey	Solving problems on recursively constructed graphs.	ACM Comput. Surv.	2008	DBLP DOI BibTeX RDF	Halin graph, branchwidth, cliquewidth, cutwidth, rankwidth, series parallel, dynamic programming, tree, Bandwidth, treewidth, cograph, pathwidth
2	Michael Lampis, Georgia Kaouri, Valia Mitsou	On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures.	ISAAC	2008	DBLP DOI BibTeX RDF	Digraph decompositions, Treewidth, Parameterized Complexity
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	Frank van den Eijkhof, Hans L. Bodlaender, Arie M. C. A. Koster	Safe Reduction Rules for Weighted Treewidth.	Algorithmica	2007	DBLP DOI BibTeX RDF
2	Vida Dujmovic, David R. Wood	Graph Treewidth and Geometric Thickness Parameters.	Discrete & Computational Geometry	2007	DBLP DOI BibTeX RDF
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	Sheng-Lung Peng, Yi-Chuan Yang	On the Treewidth and Pathwidth of Biconvex Bipartite Graphs.	TAMC	2007	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender	Treewidth: Structure and Algorithms.	SIROCCO	2007	DBLP DOI BibTeX RDF
2	Yunting Lu, Yueping Li	The Minimum All-Ones Problem for Graphs with Small Treewidth.	COCOA	2007	DBLP DOI BibTeX RDF
2	Dániel Marx	Can you beat treewidth?	FOCS	2007	DBLP DOI BibTeX RDF
2	Emgad H. Bachoore, Hans L. Bodlaender	Weighted Treewidth Algorithmic Techniques and Results.	ISAAC	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	Federico Mancini	Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs.	ISAAC	2007	DBLP DOI BibTeX RDF
2	Andrew Leaver-Fay, Yuanxin Liu, Jack Snoeyink, Xueyi Wang	Faster placement of hydrogens in protein structures by dynamic programming.	ACM Journal of Experimental Algorithmics	2007	DBLP DOI BibTeX RDF	hard-sphere model, hydrogen bonds, hydrogen placement, Dynamic programming, treewidth, protein structure
2	Davide Bilò, Jörg Derungs, Luciano Gualà, Guido Proietti, Peter Widmayer	Locating Facilities on a Network to Minimize Their Average Service Radius.	ISAAC	2007	DBLP DOI BibTeX RDF	Graph radius, Graph treewidth, NP-hardness, Graph partition, Facility location problems
2	Hans L. Bodlaender	Treewidth: Characterizations, Applications, and Computations.	WG	2006	DBLP DOI BibTeX RDF
2	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
2	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
2	Yuliya Zabiyaka, Adnan Darwiche	Functional Treewidth: Bounding Complexity in the Presence of Functional Dependencies.	SAT	2006	DBLP DOI BibTeX RDF
2	Frederic Dorn, Jan Arne Telle	Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm.	LATIN	2006	DBLP DOI BibTeX RDF
2	Pierre Fraigniaud, Nicolas Nisse	Connected Treewidth and Connected Graph Searching.	LATIN	2006	DBLP DOI BibTeX RDF
2	Yngve Villanger	Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In.	LATIN	2006	DBLP DOI BibTeX RDF
2	Yong Gao	On the Threshold of Having a Linear Treewidth in Random Graphs.	COCOON	2006	DBLP DOI BibTeX RDF
2	Fedor V. Fomin, Serge Gaspers, Saket Saurabh	Branching and Treewidth Based Exact Algorithms.	ISAAC	2006	DBLP DOI BibTeX RDF
2	Marko Samer, Stefan Szeider	Constraint Satisfaction with Bounded Treewidth Revisited.	CP	2006	DBLP DOI BibTeX RDF
2	Constantinos Daskalakis, Christos H. Papadimitriou	Computing pure nash equilibria in graphical games via markov random fields.	ACM Conference on Electronic Commerce	2006	DBLP DOI BibTeX RDF	markov random fields, nash equilibrium, treewidth
2	Irit Katriel, Hans L. Bodlaender	Online topological ordering.	ACM Transactions on Algorithms	2006	DBLP DOI BibTeX RDF	graphs, online algorithms, treewidth, Dynamic algorithms, topological order
2	Pierre Fraigniaud, Nicolas Nisse	Monotony Properties of Connected Visible Graph Searching.	WG	2006	DBLP DOI BibTeX RDF	Treewidth, Graph Searching, Pathwidth
2	Prosenjit Bose, Vida Dujmovic, David R. Wood	Induced Subgraphs of Bounded Degree and Bounded Treewidth.	WG	2005	DBLP DOI BibTeX RDF
2	Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith	Algorithms Based on the Treewidth of Sparse Graphs.	WG	2005	DBLP DOI BibTeX RDF
2	Daniel Meister	Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time.	WG	2005	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender, Alexander Grigoriev, Arie M. C. A. Koster	Treewidth Lower Bounds with Brambles.	ESA	2005	DBLP DOI BibTeX RDF
2	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 DOI BibTeX RDF
2	Andrea Ferrara, Guoqiang Pan, Moshe Y. Vardi	Treewidth in Verification: Local vs. Global.	LPAR	2005	DBLP DOI BibTeX RDF
2	Jirí Fiala, Petr A. Golovach, Jan Kratochvíl	Distance Constrained Labelings of Graphs of Bounded Treewidth.	ICALP	2005	DBLP DOI BibTeX RDF
2	Arie M. C. A. Koster, Thomas Wolle, Hans L. Bodlaender	Degree-Based Treewidth Lower Bounds.	WEA	2005	DBLP DOI BibTeX RDF
2	Emgad H. Bachoore, Hans L. Bodlaender	New Upper Bound Heuristics for Treewidth.	WEA	2005	DBLP DOI BibTeX RDF
2	Albert Atserias	On Digraph Coloring Problems and Treewidth Duality.	LICS	2005	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender	Discovering Treewidth.	SOFSEM	2005	DBLP DOI BibTeX RDF
2	Vida Dujmovic, David R. Wood	Graph Treewidth and Geometric Thickness Parameters.	Graph Drawing	2005	DBLP DOI BibTeX RDF
2	Samuel Ieong, Yoav Shoham	Marginal contribution nets: a compact representation scheme for coalitional games.	ACM Conference on Electronic Commerce	2005	DBLP DOI BibTeX RDF	coalitional game theory, representation, Treewidth
2	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
2	Hans L. Bodlaender, Arie M. C. A. Koster	On the Maximum Cardinality Search Lower Bound for Treewidth.	WG	2004	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender, Arie M. C. A. Koster, Thomas Wolle	Contraction and Treewidth Lower Bounds.	ESA	2004	DBLP DOI BibTeX RDF
2	Erik D. Demaine, Mohammad Taghi Hajiaghayi	Equivalence of local treewidth and linear local treewidth and its algorithmic applications.	SODA	2004	DBLP DOI BibTeX RDF
2	Fedor V. Fomin, Dieter Kratsch, Ioan Todinca	Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In.	ICALP	2004	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender, Fedor V. Fomin	Equitable Colorings of Bounded Treewidth Graphs.	MFCS	2004	DBLP DOI BibTeX RDF
2	Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos	Bidimensional Parameters and Local Treewidth.	LATIN	2004	DBLP DOI BibTeX RDF
2	Yong Gao, Joseph C. Culberson	On the Treewidth of NK Landscapes.	GECCO	2003	DBLP DOI BibTeX RDF
2	Fedor V. Fomin, Dimitrios M. Thilikos	Dominating Sets and Local Treewidth.	ESA	2003	DBLP DOI BibTeX RDF
2	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
2	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
2	Frank van den Eijkhof, Hans L. Bodlaender	Safe Reduction Rules for Weighted Treewidth.	WG	2002	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	Jens Gustedt, Ole A. Mæhle, Jan Arne Telle	The Treewidth of Java Programs.	ALENEX	2002	DBLP DOI BibTeX RDF
2	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
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	Sven Oliver Krumke, Madhav V. Marathe, Diana Poensgen, S. S. Ravi, Hans-Christoph Wirth	Budgeted Maximum Graph Coverage.	WG	2002	DBLP DOI BibTeX RDF	budgeted maximum coverage, approximation algorithm, integer linear programming, treewidth, maximum weight matching
2	Hajo Broersma, Ton Kloks, Dieter Kratsch, Haiko Müller	A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems.	Algorithmica	2002	DBLP DOI BibTeX RDF	Asteroidal triple, Minimum fill-in, Vertex ranking, Algorithm, Complexity, Graph, Treewidth
2	Derek G. Corneil, Udi Rotics	On the Relationship between Clique-Width and Treewidth.	WG	2001	DBLP DOI BibTeX RDF
2	Anil Maheshwari, Norbert Zeh	I/O-efficient algorithms for graphs of bounded treewidth.	SODA	2001	DBLP DOI BibTeX RDF
2	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
2	Torben Hagerup	Dynamic Algorithms for Graphs of Bounded Treewidth.	Algorithmica	2000	DBLP DOI BibTeX RDF
2	David Eppstein	Diameter and Treewidth in Minor-Closed Graph Families.	Algorithmica	2000	DBLP DOI BibTeX RDF
2	Vincent Bouchitté, Ioan Todinca	Approximating the Treewidth of AT-Free Graphs.	WG	2000	DBLP DOI BibTeX RDF
2	Xiao Zhou, Syurei Tamura, Takao Nishizeki	Finding Edge-Disjoint Paths in Partial k-Trees.	Algorithmica	2000	DBLP DOI BibTeX RDF	Polynomial-time algorithm, Edge-coloring, Edge-disjoint paths, Partial k -tree, Bounded treewidth
2	Vincent Bouchitté, Ioan Todinca	Treewidth and Minimum Fill-in of Weakly Triangulated Graphs.	STACS	1999	DBLP DOI BibTeX RDF
2	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
2	Elias Dahlhaus	Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs.	WG	1998	DBLP DOI BibTeX RDF
2	Hajo Broersma, Ton Kloks, Dieter Kratsch, Haiko Müller	A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking.	WG	1998	DBLP DOI BibTeX RDF