A linear time algorithm for finding tree-decompositions of small treewidth

Keywords

Treewidth, Citation, Computer science, Tree (set theory), Time complexity

References

• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchyHans L. Bodlaender, Michael R. Fellows, Michael Hallett — 1994
• Linear algorithms on k-terminal graphsStephen T. Hedetniemi, Thomas Wimer — 1987
• Nonconstructive tools for proving polynomial-time decidabilityMichael R. Fellows, Michael A. Langston — 1988
• Linear time algorithms for NP-hard problems restricted to partial k-treesStefan Arnborg, Andrzej Proskurowski — 1989
• On search decision and the efficiency of polynomial-time algorithmsMichael R. Fellows, Michael A. Langston — 1989
• Nonconstructive Advances in Polynomial-Time ComplexityMichael R. Fellows, Michael A. Langston — 1987
• Graph Minors .XIII. The Disjoint Paths ProblemNeil Robertson, Paul Seymour — 1995
• The Pathwidth and Treewidth of CographsHans L. Bodlaender, Rolf H. Möhring — 1990
• Monadic Second-Order Evaluations on Tree-Decomposable GraphsBruno Courcelle, Mohamed Mosbah — 1991
• An algebraic theory of graph reductionStefan Arnborg, Bruno Courcelle, Andrzej Proskurowski — 1990
• The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite GraphsBruno Courcelle — 1990
• Graph Minors. II. Algorithmic Aspects of Tree-WidthNeil Robertson, Paul Seymour — 1986
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A surveyStefan Arnborg — 1985
• Graph minors. IV. Tree-width and well-quasi-orderingNeil Robertson, Paul Seymour — 1990
• Graph minors. X. Obstructions to tree-decompositionNeil Robertson, Paul Seymour — 1991
• Graph minors. V. Excluding a planar graphNeil Robertson, Paul Seymour — 1986
• Easy Problems for Tree-Decomposable GraphsStefan Arnborg, Jens Lagergren, Detlef Seese — 1991
• Complexity of finding embeddings in a k -treeStefan Arnborg, Derek G. Corneil, Andrzej Proskurowski — 1987
• An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizationsMichael R. Fellows, Michael A. Langston — 1989
• Algorithms Finding Tree-Decompositions of GraphsJiřı́ Matoušek, Robin Thomas — 1991

Cited by

• Computational study for domination problems in planar graphsMarjan Marzban — 2012
• List-coloring graphs without subdivisions and without immersionsKen‐ichi Kawarabayashi, Yusuke Kobayashi — 2012
• Graph Colouring with Input RestrictionsJian Song — 2013
• Finding Cactus Roots in Polynomial TimeEmilie Letur — 2016
• Not So Easy Problems for Tree Decomposable GraphsStefan Szeider — 2011
• The Feasibility and Use of a Minor Containment AlgorithmXiong, Liu, Michael J. Dinneen — 2000
• Augmenting Outerplanar Graphs to Meet Diameter RequirementsToshimasa Ishii — 2012
• Quantified Constraint Satisfaction and Bounded TreewidthHubie Chen — 2004
• Algorithmique de l'alignement structure-séquence d'ARN : une approche générale et paramétrée. (RNA structure-sequence alignment algorithmic : a general and parameterized approach)Philippe Rinaudo — 2012
• Methods for Interactive Constraint SatisfactionJeppe Nejsum Madsen, Master’S Thesis — 2003
• Topics in Graph Algorithms: Structural Results and Algorithmic Techniques, with ApplicationsAbu Khzam, Faisal Nabih — 2003
• Efficient algorithms for network center/covering location optimization problemsQiaosheng Shi — 2008
• New Width Parameters of GraphsMartin Vatshelle — 2012
• Constraint satisfaction, databases, and logicPhokion G. Kolaitis — 2003
• Computational Tractability: The View From MarsRodney G. Downey, Michael R. Fellows, Ulrike Stege — 1999
• Compendium of Parameterized ProblemsMarco Cesati — 2006
• Computational study on branch decomposition of planar graphsMingzhe Zhu — 2013
• Optimal Time-Space Tradeoff in Probabilistic InferenceMichael Jakl, Reinhard Pichler, Stefan Woltran — 2009
• A Model-Based Diagnosis Framework for Distributed Embedded SystemsGregory Provan — 2002
• Automata-theoretic and datalog-based solutions of monadic second-order logic evaluation problems over structures of bounded-treewidthΛαμπρινή Καλαντζή, Ευγενία Φουστούκου — 2011

Related papers

• Answer Set Solving with Bounded Treewidth RevisitedJohannes K. Fichte, Markus Hecher, Michael Morak — 2017
• Regular resolution for CNFs with almost bounded one-sided treewidthAndrea Calı̀, Igor Razgon — 2019
• Non-FPT lower bounds for structural restrictions of decision DNNFAndrea Calı̀, Florent Capelli, Igor Razgon — 2017
• Not So Easy Problems for Tree Decomposable GraphsStefan Szeider — 2011
• Exploiting Treewidth for Projected Model Counting and its LimitsJohannes K. Fichte, Michael Morak, Markus Hecher — 2018