Search results for "Treewidth"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
21	Henning Fernau, David W. Juedes	A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs.	MFCS	2004	DBLP DOI BibTeX RDF
21	Konstantin Andreev, Charles Garrod, Bruce M. Maggs, Adam Meyerson	Simultaneous Source Location.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
21	Michael R. Fellows, Stefan Szeider, Graham Wrightson	On Finding Short Resolution Refutations and Small Unsatisfiable Subsets.	IWPEC	2004	DBLP DOI BibTeX RDF
21	Yuri Rabinovich	On average distortion of embedding metrics into the line and into L1.	STOC	2003	DBLP DOI BibTeX RDF	average metric distortion, planar metrics, finite metric spaces
21	Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Raffaele Mosca	New Graph Classes of Bounded Clique-Width.	WG	2002	DBLP DOI BibTeX RDF
21	Adnan Darwiche	Decomposable negation normal form.	J. ACM	2001	DBLP DOI BibTeX RDF	Boolean functions, satisfiability, propositional logic, model-based diagnosis, knowledge compilation
21	Vincent Bouchitté, Ioan Todinca	Listing All Potential Maximal Cliques of a Graph.	STACS	2000	DBLP DOI BibTeX RDF
21	Georg Gottlob, Nicola Leone, Francesco Scarcello	Computing LOGCFL Certificates.	ICALP	1999	DBLP DOI BibTeX RDF
21	Vincent Bouchitté, Ioan Todinca	Minimal Triangulations for Graphs with "Few" Minimal Separators.	ESA	1998	DBLP DOI BibTeX RDF
21	Andreas Parra, Petra Scheffler	How to Use the Minimal Separators of a Graph for its Chordal Triangulation.	ICALP	1995	DBLP DOI BibTeX RDF
21	Stefan Arnborg	Decomposable Structures, Boolean Function Representations, and Optimization.	MFCS	1995	DBLP DOI BibTeX RDF
21	Damon Kaller, Arvind Gupta, Thomas C. Shermer	The Chi-t-Coloring Problem.	STACS	1995	DBLP DOI BibTeX RDF
21	Hans L. Bodlaender, Klaus Jansen	On the Complexity of the Maximum Cut Problem.	STACS	1994	DBLP DOI BibTeX RDF
19	Stephan Kreutzer, Siamak Tazari	Lower Bounds for the Complexity of Monadic Second-Order Logic.	LICS	2010	DBLP DOI BibTeX RDF	Parameterized Intractability, Graph Structure Theory, Treewidth, Parameterized Complexity, Finite Model Theory, Monadic Second-Order Logic
19	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
19	Vida Dujmovic, Ken-ichi Kawarabayashi, Bojan Mohar, David R. Wood	Improved upper bounds on the crossing number.	SCG	2008	DBLP DOI BibTeX RDF	convex crossing number, rectilinear crossing number, graph drawing, treewidth, crossing number, graph minors, pathwidth, maximum degree
19	Yueping Li, Yunting Lu	A Note on Root Choice for Parallel Processing of Tree Decompositions.	KES-AMSTA	2008	DBLP DOI BibTeX RDF	algorithm, parallel processing, treewidth, tree decomposition
19	Frédéric Mazoit, Nicolas Nisse	Monotonicity of Non-deterministic Graph Searching.	WG	2007	DBLP DOI BibTeX RDF	Monotonicity, Treewidth, Graph searching
19	Srinath R. Naidu, Vijay Chandru	On Synthesis of Easily Testable (k, K) Circuits.	IEEE Trans. Computers	2003	DBLP DOI BibTeX RDF	Testing, synthesis, stuck-at fault, polynomial time, treewidth, k-tree
19	Maáyan Fishelson, Dan Geiger	Optimizing exact genetic linkage computations.	RECOMB	2003	DBLP DOI BibTeX RDF	DAG models, genetic linkage analysis, superlink, bayesian networks, combinatorial optimization, greedy algorithms, probabilistic algorithms, treewidth
19	Thomas Eiter, Georg Gottlob, Kazuhisa Makino	New results on monotone dualization and generating hypergraph transversals.	STOC	2002	DBLP DOI BibTeX RDF	combinatorial enumeration, hypergraph acyclicity, limited nondeterminism, output-polynomial algorithms, transversal computation, treewidth, dualization
19	Georg Gottlob, Nicola Leone, Francesco Scarcello	The complexity of acyclic conjunctive queries.	J. ACM	2001	DBLP DOI BibTeX RDF	LOGCFL, acyclic hypergraph, degree of cyclicity, hinge, join tree, qury-idth, algorithm, parallel algorithm, constraint, CSP, database theory, constraint satisfaction problem, conjunctive query, subsumption, query containment, bounded treewidth, tree query
19	Mohammod Abul Kashem, Xiao Zhou 0001, Takao Nishizeki	An NC Parallel Algorithm for Generalized Vertex-Rankings of Partial k-Trees.	ISPAN	1997	DBLP DOI BibTeX RDF	Separator tree, Vertex-ranking, Parallel algorithm, Treewidth, Partial k-tree
19	Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, Detlef Seese	An Algebraic Theory of Graph Reduction.	J. ACM	1993	DBLP DOI BibTeX RDF	graph algebra, regular set of graphs, treewidth, graph rewriting, monadic second-order logic
15	Clément Dallard, Martin Milanic, Kenny Storgel	Treewidth versus clique number. II. Tree-independence number.	J. Comb. Theory, Ser. B	2024	DBLP DOI BibTeX RDF
15	Rutger Campbell, Katie Clinch, Marc Distel, J. Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, David R. Wood	Product structure of graph classes with bounded treewidth.	Comb. Probab. Comput.	2024	DBLP DOI BibTeX RDF
15	Parinya Chalermsook, Matthias Kaul, Matthias Mnich, Joachim Spoerhase, Sumedha Uniyal, Daniel Vaz 0001	Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter.	ACM Trans. Algorithms	2024	DBLP DOI BibTeX RDF
15	Bogdan Alecu, Vadim V. Lozin, Daniel A. Quiroz, Roman Rabinovich 0001, Igor Razgon, Viktor Zamaraev	The Treewidth and Pathwidth of Graph Unions.	SIAM J. Discret. Math.	2024	DBLP DOI BibTeX RDF
15	Robert Hickingbotham, Freddie Illingworth, Bojan Mohar, David R. Wood	Treewidth, Circle Graphs, and Circular Drawings.	SIAM J. Discret. Math.	2024	DBLP DOI BibTeX RDF
15	Patrizio Angelini, Michael A. Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani, Alessandra Tappini	Recognizing Map Graphs of Bounded Treewidth.	Algorithmica	2024	DBLP DOI BibTeX RDF
15	Jakob Greilhuber, Philipp Schepper, Philip Wellnitz	Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs.	CoRR	2024	DBLP DOI BibTeX RDF
15	Isolde Adler, Eva Fluck	Monotonicity of the cops and robber game for bounded depth treewidth.	CoRR	2024	DBLP DOI BibTeX RDF
15	Clément Dallard, Matjaz Krnc, O.-joung Kwon, Martin Milanic, Andrea Munaro, Kenny Storgel, Sebastian Wiederrecht	Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star.	CoRR	2024	DBLP DOI BibTeX RDF
15	Tesshu Hanaka, Noleen Köhler, Michael Lampis	Core Stability in Additively Separable Hedonic Games of Low Treewidth.	CoRR	2024	DBLP DOI BibTeX RDF
15	Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski	Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness.	CoRR	2024	DBLP DOI BibTeX RDF
15	Mengyu Cao, Ke Liu, Mei Lu, Zequn Lv	Treewidth of the q-Kneser graphs.	Discret. Appl. Math.	2024	DBLP DOI BibTeX RDF
15	Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono 0001, Yota Otachi	On a Spectral Lower Bound of Treewidth.	IEICE Trans. Inf. Syst.	2024	DBLP DOI BibTeX RDF
15	Chun-Hung Liu	Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth.	Discret. Math.	2024	DBLP DOI BibTeX RDF
15	Cristina Feier, Tomasz Gogacz, Filip Murlak	Evaluating Graph Queries Using Semantic Treewidth.	ICDT	2024	DBLP DOI BibTeX RDF
15	Eva Fluck, Tim Seppelt, Gian Luca Spitzer	Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth.	CSL	2024	DBLP DOI BibTeX RDF
15	Édouard Bonnet, Hugues Déprés	Twin-width can be exponential in treewidth.	J. Comb. Theory, Ser. B	2023	DBLP DOI BibTeX RDF
15	Rutger Campbell, Marc Distel, J. Pascal Gollin, Daniel J. Harvey, Kevin Hendrey, Robert Hickingbotham, Bojan Mohar, David R. Wood	Graphs of Linear Growth have Bounded Treewidth.	Electron. J. Comb.	2023	DBLP DOI BibTeX RDF
15	Aditya Jayaprakash, Mohammad R. Salavatipour	Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension.	ACM Trans. Algorithms	2023	DBLP DOI BibTeX RDF
15	Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak	Approximating Pathwidth for Graphs of Small Treewidth.	ACM Trans. Algorithms	2023	DBLP DOI BibTeX RDF
15	Shmuel Onn	Degree sequence optimization in bounded treewidth.	Optim. Lett.	2023	DBLP DOI BibTeX RDF
15	Johannes Klaus Fichte, Markus Hecher, Michael Morak, Patrick Thier, Stefan Woltran	Solving Projected Model Counting by Utilizing Treewidth and its Limits.	Artif. Intell.	2023	DBLP DOI BibTeX RDF
15	Hong-Yu Chen, Hong-Jian Lai	On the Linear Arboricity of Graphs with Treewidth at Most Four.	Graphs Comb.	2023	DBLP DOI BibTeX RDF
15	Hisao Tamaki	A contraction-recursive algorithm for treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Falko Hegerfeld, Stefan Kratsch	Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Juhi Chaudhary, Meirav Zehavi	P-matchings Parameterized by Treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Shmuel Onn	Degree Sequence Optimization in Bounded Treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Michal Wlodarczyk 0001	Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Marius Bozga, Lucas Bueri, Radu Iosif, Florian Zuleger	The Treewidth Boundedness Problem for an Inductive Separation Logic of Relations.	CoRR	2023	DBLP DOI BibTeX RDF
15	Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski 0001	Dynamic treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Lukas Drexler, Jan Höckendorff, Joshua Könen, Kevin Schewior	Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs.	CoRR	2023	DBLP DOI BibTeX RDF
15	Johannes Klaus Fichte, Markus Hecher, Michael Morak, Patrick Thier, Stefan Woltran	Solving Projected Model Counting by Utilizing Treewidth and its Limits.	CoRR	2023	DBLP DOI BibTeX RDF
15	Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý	Treewidth is NP-Complete on Cubic Graphs (and related results).	CoRR	2023	DBLP DOI BibTeX RDF
15	Isja Mannens, Jesper Nederlof	A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li 0005, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale	Tight (Double) Exponential Bounds for NP-Complete Problems: Treewidth and Vertex Cover Parameterizations.	CoRR	2023	DBLP DOI BibTeX RDF
15	Kolja Knauer, Torsten Ueckerdt	Clustered independence and bounded treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Eva Fluck, Tim Seppelt, Gian Luca Spitzer	Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Nicolas Nisse, Lucas Picasarri-Arrieta, Ignasi Sau	Redicolouring digraphs: directed treewidth and cycle-degeneracy.	CoRR	2023	DBLP DOI BibTeX RDF
15	Michael Levet, Puck Rombach, Nicholas Sieger	Logarithmic Weisfeiler-Leman and Treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Julien Baste	The Leafed Induced Subtree in chordal and bounded treewidth graphs.	CoRR	2023	DBLP DOI BibTeX RDF
15	Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz	Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results.	CoRR	2023	DBLP DOI BibTeX RDF
15	Nicolas Bousquet, Quentin Deschamps, Aline Parreau	Metric dimension parameterized by treewidth in chordal graphs.	CoRR	2023	DBLP DOI BibTeX RDF
15	Michal Wlodarczyk 0001, Meirav Zehavi	Planar Disjoint Paths, Treewidth, and Kernels.	CoRR	2023	DBLP DOI BibTeX RDF
15	Markus Hecher	Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth?	CoRR	2023	DBLP DOI BibTeX RDF
15	Bingkai Lin, Huairui Chu	FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set.	CoRR	2023	DBLP DOI BibTeX RDF
15	Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov	Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Bart M. P. Jansen, Jari J. H. de Kroon, Michal Wlodarczyk 0001	5-Approximation for $\mathcal{H}$-Treewidth Essentially as Fast as $\mathcal{H}$-Deletion Parameterized by Solution Size.	CoRR	2023	DBLP DOI BibTeX RDF
15	Édouard Bonnet, Jedrzej Hodor, Tuukka Korhonen, Tomás Masarík	Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor.	CoRR	2023	DBLP DOI BibTeX RDF
15	Parinya Chalermsook, Fedor V. Fomin, Thekla Hamm, Tuukka Korhonen, Jesper Nederlof, Ly Orgo	Polynomial-time Approximation of Independent Set Parameterized by Treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Zhao Song 0002, Tianyi Zhou 0002	Faster Sinkhorn's Algorithm with Small Treewidth.	CoRR	2023	DBLP DOI BibTeX RDF
15	Vincent Cohen-Addad, Hung Le 0001, Marcin Pilipczuk, Michal Pilipczuk	Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1.	CoRR	2023	DBLP DOI BibTeX RDF
15	Sally Dong, Guanghao Ye	Faster Min-Cost Flow on Bounded Treewidth Graphs.	CoRR	2023	DBLP DOI BibTeX RDF
15	Steven Chaplick, Steven Kelk, Ruben Meuwese, Matús Mihalák, Georgios Stamoulis	Snakes and Ladders: a Treewidth Story.	CoRR	2023	DBLP DOI BibTeX RDF
15	Loïc Magne, Christophe Paul, Abhijat Sharma, Dimitrios M. Thilikos	Edge-treewidth: Algorithmic and combinatorial properties.	Discret. Appl. Math.	2023	DBLP DOI BibTeX RDF
15	Tom C. van der Zanden, Hans L. Bodlaender, Herbert J. M. Hamers	Efficiently computing the Shapley value of connectivity games in low-treewidth graphs.	Oper. Res.	2023	DBLP DOI BibTeX RDF
15	Markus Hecher	Advanced tools and methods for treewidth-based problem solving.	it Inf. Technol.	2023	DBLP DOI BibTeX RDF
15	Klaus Metsch	On the treewidth of generalized Kneser graphs.	Australas. J Comb.	2023	DBLP BibTeX RDF
15	Julien Baste, Ignasi Sau, Dimitrios M. Thilikos	Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm.	SIAM J. Comput.	2023	DBLP DOI BibTeX RDF
15	Paulius Dilkas	Generating Random Instances of Weighted Model Counting - An Empirical Analysis with Varying Primal Treewidth.	CPAIOR	2023	DBLP DOI BibTeX RDF
15	David Eppstein, Daniel Frishberg	Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs.	ISAAC	2023	DBLP DOI BibTeX RDF
15	Joachim Gudmundsson, Yuan Sha	Shortest Beer Path Queries in Digraphs with Bounded Treewidth.	ISAAC	2023	DBLP DOI BibTeX RDF
15	Huairui Chu, Bingkai Lin	FPT Approximation Using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set.	ISAAC	2023	DBLP DOI BibTeX RDF
15	Ronghao Su, Yungang Zhu	Learning of Bounded Treewidth Bayesian Networks via A-kg.	FSDM	2023	DBLP DOI BibTeX RDF
15	Krishnendu Chatterjee, Tobias Meggendorfer, Raimundo Saona, Jakub Svoboda	Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth.	SODA	2023	DBLP DOI BibTeX RDF
15	Akanksha Agrawal 0001, Dániel Marx, Daniel Neuen, Jasper Slusallek	Computing Square Colorings on Bounded-Treewidth and Planar Graphs.	SODA	2023	DBLP DOI BibTeX RDF
15	Marthe Bonamy, Edouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek	Sparse graphs with bounded induced cycle packing number have logarithmic treewidth.	SODA	2023	DBLP DOI BibTeX RDF
15	Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz	Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs.	SODA	2023	DBLP DOI BibTeX RDF
15	Irene Heinrich, Philine Schiewe, Constantin Seebach	Non-Pool-Based Line Planning on Graphs of Bounded Treewidth.	ATMOS	2023	DBLP DOI BibTeX RDF
15	Vincent Cohen-Addad, Hung Le 0001, Marcin Pilipczuk, Michal Pilipczuk	Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1.	FOCS	2023	DBLP DOI BibTeX RDF
15	Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski 0001	Dynamic treewidth.	FOCS	2023	DBLP DOI BibTeX RDF
15	Michal Wlodarczyk 0001, Meirav Zehavi	Planar Disjoint Paths, Treewidth, and Kernels.	FOCS	2023	DBLP DOI BibTeX RDF
15	Parinya Chalermsook, Fedor V. Fomin, Thekla Hamm, Tuukka Korhonen, Jesper Nederlof, Ly Orgo	Polynomial-Time Approximation of Independent Set Parameterized by Treewidth.	ESA	2023	DBLP DOI BibTeX RDF
15	Bart M. P. Jansen, Jari J. H. de Kroon, Michal Wlodarczyk 0001	5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size.	ESA	2023	DBLP DOI BibTeX RDF
15	Isja Mannens, Jesper Nederlof	A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth.	ESA	2023	DBLP DOI BibTeX RDF
15	Michal Wlodarczyk 0001	Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth.	ICALP	2023	DBLP DOI BibTeX RDF
15	Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph	Bounded Treewidth and the Infinite Core Chase: Complications and Workarounds toward Decidable Querying.	PODS	2023	DBLP DOI BibTeX RDF