Search results for "tree-width"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
141	Isolde Adler	Tree-width and functional dependencies in databases.	PODS	2008	DBLP DOI BibTeX RDF	hypertree-width, databases, functional dependencies, conjunctive queries, tree-width
82	Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle	Boolean-Width of Graphs.	IWPEC	2009	DBLP DOI BibTeX RDF
81	Feodor F. Dragan, Chenyu Yan	Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-Width, or Clique-Width.	ISAAC	2005	DBLP DOI BibTeX RDF
74	Vadim V. Lozin	From Tree-Width to Clique-Width: Excluding a Unit Interval Graph.	ISAAC	2008	DBLP DOI BibTeX RDF	Unit interval graphs, Fixed parameter tractability, Tree-width, Clique-width
70	Frank Gurski, Egon Wanke	Minimizing NLC-Width is NP-Complete.	WG	2005	DBLP DOI BibTeX RDF
69	Isolde Adler, Mark Weyer	Tree-Width for First Order Formulae.	CSL	2009	DBLP DOI BibTeX RDF
68	Mohammad Ali Safari	D-Width: A More Natural Measure for Directed Tree Width.	MFCS	2005	DBLP DOI BibTeX RDF
66	Frank Gurski, Egon Wanke	The Clique-Width of Tree-Power and Leaf-Power Graphs.	WG	2007	DBLP DOI BibTeX RDF	tree powers, NLC-width, strictly chordal, tree-width, clique-width, leaf powers
65	Bruno Courcelle, Mamadou Moustapha Kanté	Graph Operations Characterizing Rank-Width and Balanced Graph Expressions.	WG	2007	DBLP DOI BibTeX RDF
60	Vadim V. Lozin, Martin Milanic	Tree-Width and Optimization in Bounded Degree Graphs.	WG	2007	DBLP DOI BibTeX RDF	Hereditary class of graphs, Induced Matching, Dominating set, Tree-width
55	Johann A. Makowsky	Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width.	SODA	2001	DBLP BibTeX RDF
54	Elizabeth Broering, Satyanarayana V. Lokam	Width-Based Algorithms for SAT and CIRCUIT-SAT: (Extended Abstract).	SAT	2003	DBLP DOI BibTeX RDF
53	Frank Gurski, Egon Wanke	The Tree-Width of Clique-Width Bounded Graphs Without Kn, n.	WG	2000	DBLP DOI BibTeX RDF
52	Martin Grohe, Julian Mariño	Definability and Descriptive Complexity on Databases of Bounded Tree-Width.	ICDT	1999	DBLP DOI BibTeX RDF
52	Dániel Marx	Approximating fractional hypertree width.	SODA	2009	DBLP DOI BibTeX RDF
51	Jörg Flum, Markus Frick, Martin Grohe	Query evaluation via tree-decompositions.	J. ACM	2002	DBLP DOI BibTeX RDF	Acyclic conjunctive queries, combined complexity, hypergraphs, monadic second-order logic, tree-width
51	Markus Frick, Martin Grohe	Deciding first-order properties of locally tree-decomposable structures.	J. ACM	2001	DBLP DOI BibTeX RDF	model-checking, locality, planar graphs, First-order logic, query evaluation, parameterized complexity, tree-width
50	Jan Obdrzálek	Clique-Width and Parity Games.	CSL	2007	DBLP DOI BibTeX RDF
49	Per Bjesse, James H. Kukula, Robert F. Damiano, Ted Stanion, Yunshan Zhu	Guiding SAT Diagnosis with Tree Decompositions.	SAT	2003	DBLP DOI BibTeX RDF
49	Christof Löding	Ground Tree Rewriting Graphs of Bounded Tree Width.	STACS	2002	DBLP DOI BibTeX RDF
47	Renate Garbe	Tree-width and Path-width of Comparability Graphs of interval Orders.	WG	1994	DBLP DOI BibTeX RDF
47	Jaroslav Nesetril, Patrice Ossona de Mendez	Linear time low tree-width partitions and algorithmic consequences.	STOC	2006	DBLP DOI BibTeX RDF	bounded expansion, fraternal augmentation, coloration, first order logic, subgraph isomorphism, tree-width, graph minor
46	Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith	On Digraph Width Measures in Parameterized Algorithmics.	IWPEC	2009	DBLP DOI BibTeX RDF
45	Jan Obdrzálek	DAG-width: connectivity measure for directed graphs.	SODA	2006	DBLP DOI BibTeX RDF
45	Arvind Gupta, Naomi Nishimura	Characterizing the Complexity of Subgraph Isomorphism for Graphs of Bounded Path-Width.	STACS	1996	DBLP DOI BibTeX RDF
45	David R. Wood	Queue Layouts, Tree-Width, and Three-Dimensional Graph Drawing.	FSTTCS	2002	DBLP DOI BibTeX RDF
44	Pascal Koiran, Klaus Meer	On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width.	WG	2008	DBLP DOI BibTeX RDF
44	Andreas Jakoby, Till Tantau	Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs.	FSTTCS	2007	DBLP DOI BibTeX RDF	logspace algorithms, distance problem, longest path problem, bounded tree-width, K 4-minor-free graphs, Series-parallel graphs
44	Bernd Burgstaller, Johann Blieberger, Bernhard Scholz	On the Tree Width of Ada Programs.	Ada-Europe	2004	DBLP DOI BibTeX RDF
42	Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer	DAG-Width and Parity Games.	STACS	2006	DBLP DOI BibTeX RDF
42	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
41	Erich Grädel, Lukasz Kaiser, Roman Rabinovich 0001	Directed Graphs of Entanglement Two.	FCT	2009	DBLP DOI BibTeX RDF
40	Wolfgang Espelage, Frank Gurski, Egon Wanke	Deciding Clique-Width for Graphs of Bounded Tree-Width.	WADS	2001	DBLP DOI BibTeX RDF
39	Martin Grohe	Local Tree-Width, Excluded Minors, and Approximation Algorithms.	Comb.	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C83, 05C85, 68W25
39	Jan Obdrzálek	Fast Mu-Calculus Model Checking when Tree-Width Is Bounded.	CAV	2003	DBLP DOI BibTeX RDF
39	Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Dirk Vertigan	Partitioning Graphs of Bounded Tree-Width.	Comb.	1998	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 05C15, 05C05, 05C55
39	Denis Lapoire	Recognizability Equals Monadic Second-Order Definability for Sets of Graphs of Bounded Tree-Width.	STACS	1998	DBLP DOI BibTeX RDF
39	Stephan Kreutzer	On the Parameterised Intractability of Monadic Second-Order Logic.	CSL	2009	DBLP DOI BibTeX RDF
39	Jens Lagergren, Stefan Arnborg	Finding Minimal Forbidden Minors Using a Finite Congruence.	ICALP	1991	DBLP DOI BibTeX RDF
38	Robert Mateescu, Rina Dechter	AND/OR Search Spaces and the Semantic Width of Constraint Networks.	CP	2005	DBLP DOI BibTeX RDF
37	Frank Gurski, Egon Wanke	The NLC-width and clique-width for powers of graphs of bounded tree-width.	Discret. Appl. Math.	2009	DBLP DOI BibTeX RDF
36	Pierre Fraigniaud, Cyril Gavoille	Lower Bounds for Oblivious Single-Packet End-to-End Communication.	DISC	2003	DBLP DOI BibTeX RDF	Sequence Transmission, End-to-End, Tree-Width
34	Gruia Calinescu, Cristina G. Fernandes, Bruce A. Reed	Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width.	IPCO	1998	DBLP DOI BibTeX RDF
32	Omer Giménez, Petr Hlinený, Marc Noy	Computing the Tutte Polynomial on Graphs of Bounded Clique-Width.	WG	2005	DBLP DOI BibTeX RDF	subexponential algorithm, U polynomial, cographs, clique-width, Tutte polynomial
32	Georg Gottlob, Reinhard Pichler	Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width.	ICALP	2001	DBLP DOI BibTeX RDF
31	Frank Gurski, Carolin Rehs	Forbidden Directed Minors, Directed Path-Width and Directed Tree-Width of Tree-Like Digraphs.	SOFSEM	2019	DBLP DOI BibTeX RDF
31	Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed	A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width.	FOCS	2008	DBLP DOI BibTeX RDF
31	Andrei Kotlov	Spectral Characterization of Tree-Width-Two Graphs.	Comb.	2000	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 05
31	Mikkel Thorup	Structured Programs have Small Tree-Width and Good Register Allocation (Extended Abstract).	WG	1997	DBLP DOI BibTeX RDF
31	Egon Wanke	Bounded Tree-Width and LOGCFL.	WG	1993	DBLP DOI BibTeX RDF
31	Klaus Meer	On Consistency and Width Notions for Constraint Programs with Algebraic Constraints.	FLOPS	2002	DBLP DOI BibTeX RDF	algebraic constraint satisfaction problems, backtrack-free algorithms, consistency, width
31	Martin Fürer	Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks.	ESA	2009	DBLP DOI BibTeX RDF	counting matchings, counting independent sets, bounded tree-width, efficient algorithms, characteristic polynomial
30	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
30	Michael Alekhnovich, Alexander A. Razborov	Satisfiability, Branch-Width and Tseitin Tautologies.	FOCS	2002	DBLP DOI BibTeX RDF
29	Dietmar Berwanger, Erich Grädel	Entanglement - A Measure for the Complexity of Directed Graphs with Applications to Logic and Games.	LPAR	2004	DBLP DOI BibTeX RDF
29	Mizuhito Ogawa, Zhenjiang Hu, Isao Sasano	Iterative-free program analysis.	ICFP	2003	DBLP DOI BibTeX RDF	SP term, dynamic programming, program analysis, register allocation, control flow graph, tree width, catamorphism
27	Konstantinos Georgiou, Periklis A. Papakonstantinou	Complexity and Algorithms for Well-Structured k-SAT Instances.	SAT	2008	DBLP DOI BibTeX RDF
27	Petr Hlinený	Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids.	STACS	2003	DBLP DOI BibTeX RDF	representable matroid, fixed-parameter complexity, Classification: parametrized complexity and logic in computer science. (Math subjects 05B35, 68R05, 03D05.), monadic second-order logic, branch-width
26	Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guspiel, Petr Hlinený, Filip Pokrývka, Marek Sokolowski 0001	Sparse Graphs of Twin-width 2 Have Bounded Tree-width.	CoRR	2023	DBLP DOI BibTeX RDF
26	Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guspiel, Petr Hlinený, Filip Pokrývka, Marek Sokolowski 0001	Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width.	ISAAC	2023	DBLP DOI BibTeX RDF
26	Benjamin Merlin Bumpus, Kitty Meeks, William Pettersson	Directed branch-width: A directed analogue of tree-width.	CoRR	2020	DBLP BibTeX RDF
26	Frank Gurski, Carolin Rehs	Computing directed path-width and directed tree-width of recursively defined digraphs.	CoRR	2018	DBLP BibTeX RDF
26	Frank Gurski, Carolin Rehs	Directed Path-Width and Directed Tree-Width of Directed Co-graphs.	COCOON	2018	DBLP DOI BibTeX RDF
26	Martin Fürer	A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width.	CoRR	2014	DBLP BibTeX RDF
26	O-joung Kwon, Sang-il Oum	Graphs of small rank-width are pivot-minors of graphs of small tree-width.	Discret. Appl. Math.	2014	DBLP DOI BibTeX RDF
26	Martin Fürer	A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width.	LATIN	2014	DBLP DOI BibTeX RDF
26	O-joung Kwon, Sang-il Oum	Graphs of Small Rank-width are Pivot-minors of Graphs of Small Tree-width	CoRR	2012	DBLP BibTeX RDF
26	Fedor V. Fomin, Sang-il Oum, Dimitrios M. Thilikos	Rank-width and tree-width of H-minor-free graphs.	Eur. J. Comb.	2010	DBLP DOI BibTeX RDF
26	Hans Adler, Isolde Adler	A note on clique-width and tree-width for structures	CoRR	2008	DBLP BibTeX RDF
26	Eldar Fischer, Johann A. Makowsky, Elena V. Ravve	Counting truth assignments of formulas of bounded tree-width or clique-width.	Discret. Appl. Math.	2008	DBLP DOI BibTeX RDF
26	Petr Hlinený, Sang-il Oum, Detlef Seese, Georg Gottlob	Width Parameters Beyond Tree-width and their Applications.	Comput. J.	2008	DBLP DOI BibTeX RDF
26	Wolfgang Espelage, Frank Gurski, Egon Wanke	Deciding Clique-Width for Graphs of Bounded Tree-Width.	J. Graph Algorithms Appl.	2003	DBLP DOI BibTeX RDF
26	Jinjiang Yuan	Path-width and tree-width of the join of graphs.	Ars Comb.	1996	DBLP BibTeX RDF
26	Daniel Bienstock	Graph Searching, Path-Width, Tree-Width and Related Problems (A Survey).	Reliability Of Computer And Communication Networks	1989	DBLP DOI BibTeX RDF
26	Meinolf Sellmann, Luc Mercier, Daniel H. Leventhal	The Linear Programming Polytope of Binary Constraint Problems with Bounded Tree-Width.	CPAIOR	2007	DBLP DOI BibTeX RDF	integer programming, constraint programming, cutting planes, polyhedral combinatorics
25	Vida Dujmovic, David R. Wood	Tree-Partitions of k-Trees with Applications in Graph Layout.	WG	2003	DBLP DOI BibTeX RDF
24	Bruno Courcelle, Andrew Twigg	Compact Forbidden-Set Routing.	STACS	2007	DBLP DOI BibTeX RDF	Algorithms, compact routing, labelling schemes
24	Frank Gurski, Egon Wanke	Vertex Disjoint Paths on Clique-Width Bounded Graphs.	LATIN	2004	DBLP DOI BibTeX RDF
24	Martin Grohe	Definable Tree Decompositions.	LICS	2008	DBLP DOI BibTeX RDF	fixed point logic, descriptive complexity, tree decomposition
24	Jinbo Xu, Feng Jiao, Bonnie Berger	A Tree-Decomposition Approach to Protein Structure Prediction.	CSB	2005	DBLP DOI BibTeX RDF
24	Tommy Färnqvist, Peter Jonsson	Bounded Tree-Width and CSP-Related Problems.	ISAAC	2007	DBLP DOI BibTeX RDF	Computational complexity, constraint satisfaction, homomorphism, inapproximability, relational structure
24	Hein van der Holst	Two Tree-Width-Like Graph Invariants.	Comb.	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C83, 05C50, 15A18
24	Konstantin Yu. Gorbunov	An Estimate of the Tree-Width of a Planar Graph Which Has Not a Given Planar Grid as a Minor.	WG	1998	DBLP DOI BibTeX RDF
24	Konstantin Skodinis	The Bounded Tree-Width Problem of Context-Free Graph Languages.	WG	1997	DBLP DOI BibTeX RDF
24	David Fernández-Baca, Giora Slutzki	Optimal Parametric Search on Graphs of Bounded Tree-Width.	SWAT	1994	DBLP DOI BibTeX RDF
24	David Fernández-Baca, Giora Slutzki	Parametric Problems on Graphs of Bounded Tree-Width.	SWAT	1992	DBLP DOI BibTeX RDF
23	Aurélie Favier, Simon de Givry, Philippe Jégou	Exploiting Problem Structure for Solution Counting.	CP	2009	DBLP DOI BibTeX RDF
23	Stefan Arnborg, Jens Lagergren, Detlef Seese	Problems Easy for Tree-Decomposable Graphs (Extended Abstract).	ICALP	1988	DBLP DOI BibTeX RDF
22	Jörg Flum, Markus Frick, Martin Grohe	Query Evaluation via Tree-Decompositions.	ICDT	2001	DBLP DOI BibTeX RDF
21	Petr Skoda 0001	Computability of Width of Submodular Partition Functions.	IWOCA	2009	DBLP DOI BibTeX RDF
21	Akio Fujiyoshi	A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata.	Int. J. Found. Comput. Sci.	2017	DBLP DOI BibTeX RDF
21	Akio Fujiyoshi	A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata.	CIAA	2016	DBLP DOI BibTeX RDF
21	Nicholas Korpelainen, Vadim V. Lozin	Bipartite Graphs of Large Clique-Width.	IWOCA	2009	DBLP DOI BibTeX RDF	Hereditary class, Tree-width, Clique-width
21	Mohamed Amine Boutiche	Control of Some Graph Invariants in Dynamic Routing.	MCO	2008	DBLP DOI BibTeX RDF	Tree length, Routing, Graphs, Topology Control, Tree Decomposition, Tree width
21	Ken-ichi Kawarabayashi, Bruce A. Reed	Computing crossing number in linear time.	STOC	2007	DBLP DOI BibTeX RDF	linear time algorithm, crossing number, tree-width
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	Fedor V. Fomin, Dimitrios M. Thilikos	Dominating sets in planar graphs: branch-width and exponential speed-up.	SODA	2003	DBLP BibTeX RDF	Planar Graph, Dominating Set, Tree-width, Fixed Parameter Algorithm, Branch-width
21	Xiao Zhou 0001, Syurei Tamura, Takao Nishizeki	Finding Edge-Disjoint Paths in Partial k-Trees (Extended Abstract).	ISAAC	1996	DBLP DOI BibTeX RDF	bounded tree-width, polynomial-time algorithm, edge-coloring, edge-disjoint paths, partial k-tree
21	Jens Lagergren	Efficient Parallel Algorithms for Tree-Decomposition and Related Problems	FOCS	1990	DBLP DOI BibTeX RDF	sequential time complexity, monadic second order properties, linear extended monadic second order extremum problems, concurrent-read, concurrent-write parallel random access machine, enumeration problems, parallel algorithms, graphs, tree-decomposition, tree width, CRCW PRAM
19	Stefan Szeider	On Fixed-Parameter Tractable Parameterizations of SAT.	SAT	2003	DBLP DOI BibTeX RDF