Search results for "Treewidth"

Hits ?▲	Authors	Title	Venue	Year	Link
15	Édouard Bonnet, Nidhi Purohit	Metric Dimension Parameterized By Treewidth.	Algorithmica	2021	DBLP DOI BibTeX RDF
15	Gregory Rosenthal	Beating Treewidth for Average-Case Subgraph Isomorphism.	Algorithmica	2021	DBLP DOI BibTeX RDF
15	Therese Biedl, Saeed Mehrabi 0001	On Orthogonally Guarding Orthogonal Polygons with Bounded Treewidth.	Algorithmica	2021	DBLP DOI BibTeX RDF
15	Yan Li, Xin Zhang 0017	Equitable list tree-coloring of bounded treewidth graphs.	Theor. Comput. Sci.	2021	DBLP DOI BibTeX RDF
15	Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone	A (probably) optimal algorithm for Bisection on bounded-treewidth graphs.	Theor. Comput. Sci.	2021	DBLP DOI BibTeX RDF
15	Hans L. Bodlaender, Nick Brettell, Matthew Johnson 0002, Giacomo Paesani, Daniël Paulusma, Erik Jan van Leeuwen	Steiner trees for hereditary graph classes: A treewidth perspective.	Theor. Comput. Sci.	2021	DBLP DOI BibTeX RDF
15	Eduard Eiben, Robert Ganian, Thekla Hamm, O-joung Kwon	Measuring what matters: A hybrid approach to dynamic programming with treewidth.	J. Comput. Syst. Sci.	2021	DBLP DOI BibTeX RDF
15	Eduard Eiben, Daniel Lokshtanov, Amer E. Mouawad	Bisection of bounded treewidth graphs by convolutions.	J. Comput. Syst. Sci.	2021	DBLP DOI BibTeX RDF
15	Ludmila Glinskih, Dmitry Itsykson	On Tseitin Formulas, Read-Once Branching Programs and Treewidth.	Theory Comput. Syst.	2021	DBLP DOI BibTeX RDF
15	Dániel Marx, Govind S. Sankar, Philipp Schepper	Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth.	CoRR	2021	DBLP BibTeX RDF
15	Aditya Jayaprakash, Mohammad R. Salavatipour	Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension.	CoRR	2021	DBLP BibTeX RDF
15	Tuukka Korhonen	Single-Exponential Time 2-Approximation Algorithm for Treewidth.	CoRR	2021	DBLP BibTeX RDF
15	Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo	A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time.	CoRR	2021	DBLP BibTeX RDF
15	Jacob Focke, Dániel Marx, Pawel Rzazewski	Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds.	CoRR	2021	DBLP BibTeX RDF
15	Zdenek Dvorák 0001, Abhiruk Lahiri	Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs.	CoRR	2021	DBLP BibTeX RDF
15	Michael Lampis	Minimum Stable Cut and Treewidth.	CoRR	2021	DBLP BibTeX RDF
15	Julien Baste, Ignasi Sau, Dimitrios M. Thilikos	Hitting minors on bounded treewidth graphs. III. Lower bounds.	CoRR	2021	DBLP BibTeX RDF
15	Dániel Marx, Govind S. Sankar, Philipp Schepper	Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard).	CoRR	2021	DBLP BibTeX RDF
15	Karl Bringmann, Jasper Slusallek	Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal.	CoRR	2021	DBLP BibTeX RDF
15	Arnold Filtser, Hung Le 0001	Clan Embeddings into Trees, and Low Treewidth Graphs.	CoRR	2021	DBLP 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.	CoRR	2021	DBLP BibTeX RDF
15	Shaohua Li 0005, Marcin Pilipczuk	Hardness of Metric Dimension in Graphs of Constant Treewidth.	CoRR	2021	DBLP BibTeX RDF
15	Viktor Besin, Markus Hecher, Stefan Woltran	Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs.	CoRR	2021	DBLP BibTeX RDF
15	David Eppstein, Daniel Frishberg	Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs.	CoRR	2021	DBLP BibTeX RDF
15	Zdenek Dvorák 0001	Approximation metatheorem for fractionally treewidth-fragile graphs.	CoRR	2021	DBLP BibTeX RDF
15	Hauke Brinkop, Klaus Jansen, Tim Weißenfels	An optimal FPT algorithm parametrized by treewidth for Weighted-Max-Bisection given a tree decomposition as advice assuming SETH and the hardness of MinConv.	CoRR	2021	DBLP BibTeX RDF
15	Martin Fürer, Carlos Hoppen, Vilmar Trevisan	Efficient diagonalization of symmetric matrices associated with graphs of small treewidth.	CoRR	2021	DBLP BibTeX RDF
15	Mitchell Black, Amir Nayyeri	Finding surfaces in simplicial complexes with bounded-treewidth 1-skeleton.	CoRR	2021	DBLP BibTeX RDF
15	Julien Baste, Ignasi Sau, Dimitrios M. Thilikos	Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms.	CoRR	2021	DBLP BibTeX RDF
15	Kolja Knauer, Hoang La, Petru Valicov	Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth.	CoRR	2021	DBLP BibTeX RDF
15	Chethan Kamath, Karen Klein, Krzysztof Pietrzak	On Treewidth, Separators and Yao's Garbling.	IACR Cryptol. ePrint Arch.	2021	DBLP BibTeX RDF
15	Valentin Bartier, Nicolas Bousquet, Marc Heinrich	Recoloring graphs of treewidth 2.	Discret. Math.	2021	DBLP DOI BibTeX RDF
15	Fábio Botler, Cristina G. Fernandes, Juan Gutiérrez	On Tuza's conjecture for triangulations and graphs with small treewidth.	Discret. Math.	2021	DBLP DOI BibTeX RDF
15	Viktor Besin, Markus Hecher, Stefan Woltran	Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs.	Theory Pract. Log. Program.	2021	DBLP DOI BibTeX RDF
15	Ignasi Sau, Uéverton dos Santos Souza	Hitting forbidden induced subgraphs on bounded treewidth graphs.	Inf. Comput.	2021	DBLP DOI BibTeX RDF
15	Ke Liu, Mei Lu	Complete-Subgraph-Transversal-Sets problem on bounded treewidth graphs.	J. Comb. Optim.	2021	DBLP DOI BibTeX RDF
15	Karolina Okrasa, Pawel Rzazewski	Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs.	SIAM J. Comput.	2021	DBLP DOI BibTeX RDF
15	Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon	(Theta, triangle)-free and (even hole, K4)-free graphs. Part 2: Bounds on treewidth.	J. Graph Theory	2021	DBLP DOI BibTeX RDF
15	Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour	Induced subgraphs of bounded treewidth and the container method.	SODA	2021	DBLP DOI BibTeX RDF
15	Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak	Approximating Pathwidth for Graphs of Small Treewidth.	SODA	2021	DBLP DOI BibTeX RDF
15	Miguel Romero 0001, Marcin Wrochna, Stanislav Zivný	Treewidth-Pliability and PTAS for Max-CSPs.	SODA	2021	DBLP DOI BibTeX RDF
15	Mahdi Belbasi, Martin Fürer	An Improvement of Reed's Treewidth Approximation.	WALCOM	2021	DBLP DOI BibTeX RDF
15	Toshiki Saitoh, Ryo Yoshinaka, Hans L. Bodlaender	Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes.	WALCOM	2021	DBLP DOI BibTeX RDF
15	Chethan Kamath, Karen Klein, Krzysztof Pietrzak	On Treewidth, Separators and Yao's Garbling.	TCC (2)	2021	DBLP DOI BibTeX RDF
15	Tuukka Korhonen	A Single-Exponential Time 2-Approximation Algorithm for Treewidth.	FOCS	2021	DBLP DOI BibTeX RDF
15	Zdenek Dvorák 0001, Abhiruk Lahiri	Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs.	ESA	2021	DBLP DOI BibTeX RDF
15	Dániel Marx, Govind S. Sankar, Philipp Schepper	Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth.	ICALP	2021	DBLP DOI BibTeX RDF
15	Michael Lampis	Minimum Stable Cut and Treewidth.	ICALP	2021	DBLP DOI BibTeX RDF
15	Karl Bringmann, Jasper Slusallek	Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal.	ICALP	2021	DBLP DOI BibTeX RDF
15	Gabriel L. Duarte, Mateus de Oliveira Oliveira, Uéverton S. Souza	Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances.	MFCS	2021	DBLP DOI BibTeX RDF
15	Jorge Fandinno, Markus Hecher	Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard.	AAAI	2021	DBLP DOI BibTeX RDF
15	Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider	Turbocharging Treewidth-Bounded Bayesian Network Structure Learning.	AAAI	2021	DBLP DOI BibTeX RDF
15	Thomas Eiter, Markus Hecher, Rafael Kiesel	Treewidth-Aware Cycle Breaking for Algebraic Answer Set Counting.	KR	2021	DBLP DOI BibTeX RDF
15	Eric Goles 0001, Pedro Montealegre 0001, Martín Ríos Wilson, Guillaume Theyssier	On the Impact of Treewidth in the Computational Complexity of Freezing Dynamics.	CiE	2021	DBLP DOI BibTeX RDF
15	Sally Dong, Yin Tat Lee, Guanghao Ye	A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path.	STOC	2021	DBLP DOI BibTeX RDF
15	Arnold Filtser, Hung Le 0001	Clan embeddings into trees, and low treewidth graphs.	STOC	2021	DBLP DOI BibTeX RDF
15	Bertrand Marchand, Yann Ponty, Laurent Bulteau	Tree Diet: Reducing the Treewidth to Unlock FPT Algorithms in RNA Bioinformatics.	WABI	2021	DBLP DOI BibTeX RDF
15	Céline Scornavacca, Mathias Weller	Treewidth-Based Algorithms for the Small Parsimony Problem on Networks.	WABI	2021	DBLP DOI BibTeX RDF
15	David Eppstein, Daniel Frishberg, William Maxwell	On the Treewidth of Hanoi Graphs.	FUN	2021	DBLP DOI BibTeX RDF
15	Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Andreas Pavlogiannis	Quantitative Verification on Product Graphs of Small Treewidth.	FSTTCS	2021	DBLP DOI BibTeX RDF
15	Johannes Klaus Fichte, Markus Hecher, Yasir Mahmood 0002, Arne Meier	Decomposition-Guided Reductions for Argumentation and Treewidth.	IJCAI	2021	DBLP DOI BibTeX RDF
15	Shaohua Li 0005, Marcin Pilipczuk	Hardness of Metric Dimension in Graphs of Constant Treewidth.	IPEC	2021	DBLP DOI BibTeX RDF
15	Markus Hecher	Advanced tools and methods for treewidth-based problem solving (PDF / PS)		2021	RDF
15	Petr Kolman, Martin Koutecký, Hans Raj Tiwary	Extension Complexity, MSO Logic, and Treewidth.	Discret. Math. Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
15	Amir Kafshdar Goharshady, Fatemeh Mohammadi	An efficient algorithm for computing network reliability in small treewidth.	Reliab. Eng. Syst. Saf.	2020	DBLP DOI BibTeX RDF
15	Julien Baste, Ignasi Sau, Dimitrios M. Thilikos	Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds.	SIAM J. Discret. Math.	2020	DBLP DOI BibTeX RDF
15	Julien Baste, Ignasi Sau, Dimitrios M. Thilikos	Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
15	Cédric Bentz, Pierre Le Bodic	Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
15	Dehia Ait-Ferhat, Vincent Juliard, Gautier Stauffer, J. Andres Torres	The k-path coloring problem in graphs of bounded treewidth: An application in integrated circuit manufacturing.	Oper. Res. Lett.	2020	DBLP DOI BibTeX RDF
15	David A. Cohen, Martin C. Cooper, Artem Kaznatcheev, Mark Wallace 0001	Steepest ascent can be exponential in bounded treewidth problems.	Oper. Res. Lett.	2020	DBLP DOI BibTeX RDF
15	Julien Baste, Ignasi Sau, Dimitrios M. Thilikos	Hitting minors on bounded treewidth graphs. III. Lower bounds.	J. Comput. Syst. Sci.	2020	DBLP DOI BibTeX RDF
15	Bernhard Bliem, Michael Morak, Marius Moldovan, Stefan Woltran	The Impact of Treewidth on Grounding and Solving of Answer Set Programs.	J. Artif. Intell. Res.	2020	DBLP DOI BibTeX RDF
15	Laura Merker, Torsten Ueckerdt	The Local Queue Number of Graphs with Bounded Treewidth.	CoRR	2020	DBLP BibTeX RDF
15	David Eppstein, Daniel Frishberg, William Maxwell	On the treewidth of Hanoi graphs.	CoRR	2020	DBLP BibTeX RDF
15	Rémy Belmonte, Eun Jung Kim 0002, Michael Lampis, Valia Mitsou, Yota Otachi	Grundy Distinguishes Treewidth from Pathwidth.	CoRR	2020	DBLP BibTeX RDF
15	Simon Schierreich, Ondrej Suchý	Waypoint Routing on Bounded Treewidth Graphs.	CoRR	2020	DBLP BibTeX RDF
15	Ali Asadi, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Kiarash Mohammadi, Andreas Pavlogiannis	Faster Algorithms for Quantitative Analysis of Markov Chains and Markov Decision Processes with Small Treewidth.	CoRR	2020	DBLP BibTeX RDF
15	Flavia Bonomo-Braberman, Carolina Lucía Gonzalez	The generalized locally checkable problem in bounded treewidth graphs.	CoRR	2020	DBLP BibTeX RDF
15	Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le 0001	On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs.	CoRR	2020	DBLP BibTeX RDF
15	Markus Hecher, Jorge Fandinno	Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard.	CoRR	2020	DBLP BibTeX RDF
15	Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone	An optimal algorithm for Bisection for bounded-treewidth graphs.	CoRR	2020	DBLP BibTeX RDF
15	Sally Dong, Yin Tat Lee, Guanghao Ye	A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path.	CoRR	2020	DBLP BibTeX RDF
15	Fábio Botler, Cristina G. Fernandes, Juan Gutiérrez	On Tuza's conjecture for triangulations and graphs with small treewidth.	CoRR	2020	DBLP BibTeX RDF
15	Mahdi Belbasi, Martin Fürer	An Improvement of Reed's Treewidth Approximation.	CoRR	2020	DBLP BibTeX RDF
15	Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse	Approximate Turing Kernelization for Problems Parameterized by Treewidth.	CoRR	2020	DBLP BibTeX RDF
15	Ignasi Sau, Uéverton S. Souza	Hitting forbidden induced subgraphs on bounded treewidth graphs.	CoRR	2020	DBLP BibTeX RDF
15	Marc Heinrich	Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth.	CoRR	2020	DBLP BibTeX RDF
15	P. R. Vaidyanathan, Stefan Szeider	Turbocharging Treewidth-Bounded Bayesian Network Structure Learning.	CoRR	2020	DBLP BibTeX RDF
15	Karolina Okrasa, Marta Piecyk, Pawel Rzazewski	Full complexity classification of the list homomorphism problem for bounded-treewidth graphs.	CoRR	2020	DBLP BibTeX RDF
15	Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, O-joung Kwon	Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth.	CoRR	2020	DBLP BibTeX RDF
15	Dániel Marx	Four short stories on surprising algorithmic uses of treewidth.	CoRR	2020	DBLP BibTeX RDF
15	Hans L. Bodlaender, Nick Brettell, Matthew Johnson 0002, Giacomo Paesani, Daniël Paulusma, Erik Jan van Leeuwen	Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective.	CoRR	2020	DBLP BibTeX RDF
15	Johannes Klaus Fichte, Markus Hecher, Patrick Thier, Stefan Woltran	Exploiting Database Management Systems and Treewidth for Counting.	CoRR	2020	DBLP BibTeX RDF
15	Eric Goles 0001, Pedro Montealegre 0001, Martín Ríos Wilson, Guillaume Theyssier	On the impact of treewidth in the computational complexity of freezing dynamics.	CoRR	2020	DBLP BibTeX RDF
15	Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon	(Theta, triangle)-free and (even hole, K4)-free graphs. Part 2 : bounds on treewidth.	CoRR	2020	DBLP BibTeX RDF
15	Clément Dallard, Martin Milanic, Kenny Storgel	Treewidth versus clique number in graph classes with a forbidden structure.	CoRR	2020	DBLP BibTeX RDF
15	Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, Philipp Zschoche	As Time Goes By: Reflections on Treewidth for Temporal Graphs.	CoRR	2020	DBLP BibTeX RDF
15	Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak	Approximating pathwidth for graphs of small treewidth.	CoRR	2020	DBLP BibTeX RDF
15	Toshiki Saitoh, Ryo Yoshinaka, Hans L. Bodlaender	Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Intersection Graph Classes.	CoRR	2020	DBLP BibTeX RDF
15	Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour	Induced subgraphs of bounded treewidth and the container method.	CoRR	2020	DBLP BibTeX RDF