Search results for "treewidth"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
36	Albert Atserias	On Digraph Coloring Problems and Treewidth Duality.	LICS	2005	DBLP DOI BibTeX RDF
36	Prosenjit Bose, Vida Dujmovic, David R. Wood	Induced Subgraphs of Bounded Degree and Bounded Treewidth.	WG	2005	DBLP DOI BibTeX RDF
36	Vida Dujmovic, David R. Wood	Graph Treewidth and Geometric Thickness Parameters.	GD	2005	DBLP DOI BibTeX RDF
36	Hans L. Bodlaender	Discovering Treewidth.	SOFSEM	2005	DBLP DOI BibTeX RDF
36	Torben Hagerup	Dynamic Algorithms for Graphs of Bounded Treewidth.	Algorithmica	2000	DBLP DOI BibTeX RDF
36	David Eppstein	Diameter and Treewidth in Minor-Closed Graph Families.	Algorithmica	2000	DBLP DOI BibTeX RDF
36	Torben Hagerup	Dynamic Algorithms for Graphs of Bounded Treewidth.	ICALP	1997	DBLP DOI BibTeX RDF
36	Hans L. Bodlaender	Treewidth: Algorithmic Techniques and Results.	MFCS	1997	DBLP DOI BibTeX RDF
36	Shiva Chaudhuri, Christos D. Zaroliagis	Shortest Path Queries in Digraphs of Small Treewidth.	ICALP	1995	DBLP DOI BibTeX RDF
36	Ton Kloks, Hans L. Bodlaender, Haiko Müller, Dieter Kratsch	Computing Treewidth and Minimum Fill-In: All You Need are the Minimal Separators. (Erratum: ESA 1994: 508)	ESA	1993	DBLP DOI BibTeX RDF
36	Hans L. Bodlaender	Dynamic Algorithms for Graphs with Treewidth 2.	WG	1993	DBLP DOI BibTeX RDF
36	Ton Kloks, Dieter Kratsch	Treewidth of Bipartite Graphs.	STACS	1993	DBLP DOI BibTeX RDF
36	Hans L. Bodlaender, John R. Gilbert, Ton Kloks, Hjálmtyr Hafsteinsson	Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height.	WG	1991	DBLP DOI BibTeX RDF
36	Hans L. Bodlaender	Improved Self-Reduction Algorithms for Graphs with Bounded Treewidth.	WG	1989	DBLP DOI BibTeX RDF
33	Zhe Nie, Yueping Li, Xiaohong Zhou	Optimal Path Cover for Graphs of Small Treewidth.	NCM (1)	2008	DBLP DOI BibTeX RDF	route design, algorithm, treewidth, path cover
33	Hans L. Bodlaender	A linear time algorithm for finding tree-decompositions of small treewidth.	STOC	1993	DBLP DOI BibTeX RDF	graph algorithms, treewidth, graph minors, pathwidth, partial k-trees
32	Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca	Constructing Brambles.	MFCS	2009	DBLP DOI BibTeX RDF
32	N. R. Aravind, C. R. Subramanian 0001	Forbidden Subgraph Colorings and the Oriented Chromatic Number.	IWOCA	2009	DBLP DOI BibTeX RDF
32	Nysret Musliu	An Iterative Heuristic Algorithm for Tree Decomposition.	Recent Advances in Evolutionary Computation for Combinatorial Optimization	2008	DBLP DOI BibTeX RDF	Heuristics, Constraint Satisfaction Problem, Tree Decomposition, Graph Decomposition, Iterated Local Search
32	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
32	Naomi Nishimura, Prabhakar Ragde, Stefan Szeider	Solving #SAT using vertex covers.	Acta Informatica	2007	DBLP DOI BibTeX RDF
32	Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch	Exact Algorithms for Graph Homomorphisms.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
32	Nysret Musliu	Generation of Tree Decompositions by Iterated Local Search.	EvoCOP	2007	DBLP DOI BibTeX RDF
32	Georg Gottlob, Gianluigi Greco	On the complexity of combinatorial auctions: structured item graphs and hypertree decomposition.	EC	2007	DBLP DOI BibTeX RDF	hypertree decompositions, combinatorial auctions, hypergraphs
32	Miquel Ramírez, Hector Geffner	Structural Relaxations by Variable Renaming and Their Compilation for Solving MinCostSAT.	CP	2007	DBLP DOI BibTeX RDF
32	Naomi Nishimura, Prabhakar Ragde, Stefan Szeider	Solving #SAT Using Vertex Covers.	SAT	2006	DBLP DOI BibTeX RDF
32	Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch	Exact Algorithms for Graph Homomorphisms.	FCT	2005	DBLP DOI BibTeX RDF
32	Douglas E. Carroll, Ashish Goel	Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families.	ESA	2004	DBLP DOI BibTeX RDF
32	L. Sunil Chandran, Telikepalli Kavitha, C. R. Subramanian 0001	Isoperimetric Inequalities and the Width Parameters of Graphs.	COCOON	2003	DBLP DOI BibTeX RDF
32	Georg Gottlob, Nicola Leone, Francesco Scarcello	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width. (PDF / PS)	PODS	2001	DBLP DOI BibTeX RDF
32	Ljubomir Perkovic, Bruce A. Reed	An Improved Algorithm for Finding Tree Decompositions of Small Width.	WG	1999	DBLP DOI BibTeX RDF
32	Koichi Yamazaki, Hans L. Bodlaender, Babette de Fluiter, Dimitrios M. Thilikos	Isomorphism for Graphs of Bounded Distance Width.	CIAC	1997	DBLP DOI BibTeX RDF
32	Nick D. Dendris, Lefteris M. Kirousis, Dimitrios M. Thilikos	Fugitive-Search Games on Graphs and Related Parameters.	WG	1994	DBLP DOI BibTeX RDF
32	Michael R. Fellows, Michael T. Hallett, Harold T. Wareham	DNA Physical Mapping: Three Ways Difficult.	ESA	1993	DBLP DOI BibTeX RDF
32	Hans L. Bodlaender, Michael R. Fellows, Tandy J. Warnow	Two Strikes Against Perfect Phylogeny.	ICALP	1992	DBLP DOI BibTeX RDF
29	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
29	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
29	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
29	Andrew Leaver-Fay, Yuanxin Liu, Jack Snoeyink, Xueyi Wang	Faster placement of hydrogens in protein structures by dynamic programming.	ACM J. Exp. Algorithmics	2007	DBLP DOI BibTeX RDF	hard-sphere model, hydrogen bonds, hydrogen placement, Dynamic programming, treewidth, protein structure
29	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
29	Irit Katriel, Hans L. Bodlaender	Online topological ordering.	ACM Trans. Algorithms	2006	DBLP DOI BibTeX RDF	graphs, online algorithms, treewidth, Dynamic algorithms, topological order
29	Constantinos Daskalakis, Christos H. Papadimitriou	Computing pure nash equilibria in graphical games via markov random fields.	EC	2006	DBLP DOI BibTeX RDF	markov random fields, nash equilibrium, treewidth
29	Samuel Ieong, Yoav Shoham	Marginal contribution nets: a compact representation scheme for coalitional games.	EC	2005	DBLP DOI BibTeX RDF	coalitional game theory, representation, Treewidth
29	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
29	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
29	Xiao Zhou 0001, 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
29	Prosenjit Bose, Vida Dujmovic, Mehrnoosh Javarsineh, Pat Morin, David R. Wood	Separating layered treewidth and row treewidth.	Discret. Math. Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
29	Prosenjit Bose, Vida Dujmovic, Mehrnoosh Javarsineh, Pat Morin, David R. Wood	Separating layered treewidth and row treewidth.	CoRR	2021	DBLP BibTeX RDF
29	Julien Baste	Treewidth: algorithmic, combinatorial, and practical aspects. (Treewidth: aspects algorithmiques, combinatoires et pratiques).		2017	RDF
25	Jirí Fiala 0001, Petr A. Golovach, Jan Kratochvíl	Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover.	TAMC	2009	DBLP DOI BibTeX RDF
25	Reinhard Pichler, Stefan Rümmele, Stefan Woltran	Belief Revision with Bounded Treewidth.	LPNMR	2009	DBLP DOI BibTeX RDF
25	Michael R. Fellows, Danny Hermelin, Frances A. Rosamond	Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs.	IWPEC	2009	DBLP DOI BibTeX RDF
25	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
25	Sheng-Lung Peng, Yi-Chuan Yang	On the Treewidth and Pathwidth of Biconvex Bipartite Graphs.	TAMC	2007	DBLP DOI BibTeX RDF
25	Yunting Lu, Yueping Li	The Minimum All-Ones Problem for Graphs with Small Treewidth.	COCOA	2007	DBLP DOI BibTeX RDF
25	Hans L. Bodlaender	Treewidth: Structure and Algorithms.	SIROCCO	2007	DBLP DOI BibTeX RDF
25	Fedor V. Fomin, Serge Gaspers, Saket Saurabh 0001	Branching and Treewidth Based Exact Algorithms.	ISAAC	2006	DBLP DOI BibTeX RDF
25	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
25	Yong Gao 0001	On the Threshold of Having a Linear Treewidth in Random Graphs.	COCOON	2006	DBLP DOI BibTeX RDF
25	Emgad H. Bachoore, Hans L. Bodlaender	New Upper Bound Heuristics for Treewidth.	WEA	2005	DBLP DOI BibTeX RDF
25	Joachim Kneis, Daniel Mölle, Stefan Richter 0001, Peter Rossmanith	Algorithms Based on the Treewidth of Sparse Graphs.	WG	2005	DBLP DOI BibTeX RDF
25	Daniel Meister 0001	Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time.	WG	2005	DBLP DOI BibTeX RDF
25	Fedor V. Fomin, Dieter Kratsch, Ioan Todinca	Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In.	ICALP	2004	DBLP DOI BibTeX RDF
25	Hans L. Bodlaender, Fedor V. Fomin	Equitable Colorings of Bounded Treewidth Graphs.	MFCS	2004	DBLP DOI BibTeX RDF
25	Hans L. Bodlaender, Arie M. C. A. Koster	On the Maximum Cardinality Search Lower Bound for Treewidth.	WG	2004	DBLP DOI BibTeX RDF
25	Anil Maheshwari, Norbert Zeh	I/O-efficient algorithms for graphs of bounded treewidth.	SODA	2001	DBLP BibTeX RDF
25	Vincent Bouchitté, Ioan Todinca	Approximating the Treewidth of AT-Free Graphs.	WG	2000	DBLP DOI BibTeX RDF
25	Vincent Bouchitté, Ioan Todinca	Treewidth and Minimum Fill-in of Weakly Triangulated Graphs.	STACS	1999	DBLP DOI BibTeX RDF
25	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
25	Elias Dahlhaus	Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs.	WG	1998	DBLP DOI BibTeX RDF
25	Hajo Broersma, Elias Dahlhaus, Ton Kloks	Algorithms for the Treewidth and Minimum Fill-in of HHD-Free Graphs.	WG	1997	DBLP DOI BibTeX RDF	MSC 68R10
25	Babette de Fluiter, Hans L. Bodlaender	Parallel Algorithms for Treewidth Two.	WG	1997	DBLP DOI BibTeX RDF
25	Manfred Wiegers	The k-section of Treewidth Restricted Graphs.	MFCS	1990	DBLP DOI BibTeX RDF
25	Hans L. Bodlaender, Rolf H. Möhring	The Pathwidth and Treewidth of Cographs.	SWAT	1990	DBLP DOI BibTeX RDF
21	Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, Saket Saurabh 0001	The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Max-leaf, Well-quasiordering, Bandwidth, Kernelization, Parameterized complexity
21	Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant	On the complexity of Nash equilibria of action-graph games.	SODA	2009	DBLP DOI BibTeX RDF
21	Marek Cygan, Marcin Pilipczuk	Exact and Approximate Bandwidth.	ICALP (1)	2009	DBLP DOI BibTeX RDF
21	Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi	Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs.	ICALP (1)	2009	DBLP DOI BibTeX RDF
21	Frank Kammer, Torsten Tholey	The k-Disjoint Paths Problem on Chordal Graphs.	WG	2009	DBLP DOI BibTeX RDF
21	Luca Pulina, Armando Tacchella	Hard QBF Encodings Made Easy: Dream or Reality?	AI*IA	2009	DBLP DOI BibTeX RDF
21	Rosa Enciso, Michael R. Fellows, Jiong Guo, Iyad A. Kanj, Frances A. Rosamond, Ondrej Suchý	What Makes Equitable Connected Partition Easy.	IWPEC	2009	DBLP DOI BibTeX RDF
21	Petr A. Golovach, Dimitrios M. Thilikos	Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms.	IWPEC	2009	DBLP DOI BibTeX RDF	Bounded length disjoint paths, Bounded length cuts, Parameterized Complexity, Parameterized Algorithms
21	Frank Kammer, Torsten Tholey	The Complexity of Minimum Convex Coloring.	ISAAC	2008	DBLP DOI BibTeX RDF	Convex Coloring, Maximum Disjoint Paths Problem
21	Bonnie Berger, Rohit Singh 0001, Jinbo Xu	Graph algorithms for biological systems analysis.	SODA	2008	DBLP BibTeX RDF
21	Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin	On Problems without Polynomial Kernels (Extended Abstract).	ICALP (1)	2008	DBLP DOI BibTeX RDF
21	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
21	Johannes Köbler, Oleg Verbitsky 0001	From Invariants to Canonization in Parallel.	CSR	2008	DBLP DOI BibTeX RDF
21	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
21	Sergio Cabello, Günter Rote	Obnoxious centers in graphs.	SODA	2007	DBLP BibTeX RDF
21	Albert Atserias, Andrei A. Bulatov, Víctor Dalmau	On the Power of k -Consistency.	ICALP	2007	DBLP DOI BibTeX RDF
21	Michael R. Fellows, Frances A. Rosamond	The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number.	CiE	2007	DBLP DOI BibTeX RDF
21	Anuj Dawar, David Richerby	The Power of Counting Logics on Restricted Classes of Finite Structures.	CSL	2007	DBLP DOI BibTeX RDF
21	Benny Chor, Michael R. Fellows, Mark A. Ragan, Igor Razgon, Frances A. Rosamond, Sagi Snir	Connected Coloring Completion for General Graphs: Algorithms and Complexity.	COCOON	2007	DBLP DOI BibTeX RDF	Topics Algorithms and Complexity, Bioinformatics
21	Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, Vadim V. Lozin	Clique-Width for 4-Vertex Forbidden Subgraphs.	Theory Comput. Syst.	2006	DBLP DOI BibTeX RDF
21	Christophe Paul, Andrzej Proskurowski, Jan Arne Telle	Generation of Graphs with Bounded Branchwidth.	WG	2006	DBLP DOI BibTeX RDF
21	Foto N. Afrati, Stavros S. Cosmadakis, Eugénie Foustoucos	Datalog programs and their persistency numbers.	ACM Trans. Comput. Log.	2005	DBLP DOI BibTeX RDF	bounded-tree width hypergraphs, persistency numbers, persistent variables, program transformations, Datalog, finite automata, Boundedness
21	Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Raffaele Mosca	New Graph Classes of Bounded Clique-Width.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
21	Fedor V. Fomin, Frédéric Mazoit, Ioan Todinca	Computing Branchwidth Via Efficient Triangulations and Blocks.	WG	2005	DBLP DOI BibTeX RDF
21	Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, Vadim V. Lozin	Clique-Width for Four-Vertex Forbidden Subgraphs.	FCT	2005	DBLP DOI BibTeX RDF
21	Michael Benedikt, Luc Segoufin	Towards a Characterization of Order-Invariant Queries over Tame Structures.	CSL	2005	DBLP DOI BibTeX RDF