A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
From MaRDI portal
Publication:5691297
DOI10.1137/S0097539793251219zbMath0864.68074OpenAlexW2059372025WikidataQ56141692 ScholiaQ56141692MaRDI QIDQ5691297
Publication date: 9 June 1997
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793251219
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs, Polynomial-time algorithms for multimarginal optimal transport problems with structure, Characterizations and directed path-width of sequence digraphs, Flexible list colorings in graphs with special degeneracy conditions, Bounding the mim‐width of hereditary graph classes, Clique‐width: Harnessing the power of atoms, The firebreak problem, Edge-treewidth: algorithmic and combinatorial properties, Approximating Pathwidth for Graphs of Small Treewidth, Connected search for a lazy robber, Tangle bases: Revisited, Minimum <scp>color‐degree</scp> perfect b‐matchings, Kernelization for feedback vertex set via elimination distance to a forest, Computing connected-\(k\)-subgraph cover with connectivity requirement, The Treewidth and Pathwidth of Graph Unions, Treewidth versus clique number. II: Tree-independence number, Stability, vertex stability, and unfrozenness for special graph classes, Solving infinite-domain CSPs using the patchwork property, Allocation of indivisible items with individual preference graphs, A Modern View on Stability of Approximation, Unnamed Item, Unnamed Item, On the parameterized complexity of s-club cluster deletion problems, On the parameterized complexity of \(s\)-club cluster deletion problems, Local Hadwiger's conjecture, Linear layouts of bipartite planar graphs, Recognizing map graphs of bounded treewidth, Treewidth of the \(q\)-Kneser graphs, Locating Eigenvalues of Symmetric Matrices - A Survey, Maximizing Social Welfare in Score-Based Social Distance Games, Unnamed Item, Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs, Minor-Closed Graph Classes with Bounded Layered Pathwidth, Minimum size tree-decompositions, Bundled Crossings Revisited, Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, Minimum size tree-decompositions, How to Secure Matchings against Edge Failures, An algorithm for simultaneous backbone threading and side-chain packing, Flexible List Colorings in Graphs with Special Degeneracy Conditions, Linear transformations between dominating sets in the TAR-model, Tractable answer-set programming with weight constraints: bounded treewidth is not enough, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization, Recursive conditioning, Decomposing Quantified Conjunctive (or Disjunctive) Formulas, Counting independent sets in graphs with bounded bipartite pathwidth, Unnamed Item, Default logic and bounded treewidth, Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality, Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2, Constructing minimum changeover cost arborescenses in bounded treewidth graphs, The Parameterized Complexity of Graph Cyclability, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Feedback edge sets in temporal graphs, Backbone coloring of graphs with galaxy backbones, Backbone coloring of graphs with galaxy backbones, Unnamed Item, Walking through waypoints, The descriptive complexity of subgraph isomorphism without numerics, Clique-perfectness of complements of line graphs, Heuristic and metaheuristic methods for computing graph treewidth, Treewidth of display graphs: bounds, brambles and applications, Unnamed Item, Unnamed Item, Unnamed Item, The Valve Location Problem in Simple Network Topologies, Positive-Instance Driven Dynamic Programming for Treewidth., A Linear-Time Parameterized Algorithm for Node Unique Label Cover, Computing treewidth on the GPU, Shorter Labeling Schemes for Planar Graphs, A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES, AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH, Exploiting Structure: Location Problems on Trees and Treelike Graphs, Tree decompositions and social graphs, Unnamed Item, Unnamed Item, Unnamed Item, On Hop-Constrained Steiner Trees in Tree-Like Metrics, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, Improving robustness of next-hop routing, Safe separators for treewidth, Compatibility of unrooted phylogenetic trees is FPT, Trees, grids, and MSO decidability: from graphs to matroids, Tractability in constraint satisfaction problems: a survey, Edge-disjoint odd cycles in 4-edge-connected graphs, An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification, Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems, Outer 1-planar graphs, Structural parameterizations for boxicity, Algorithms for graphs of bounded treewidth via orthogonal range searching, A note on multiflows and treewidth, I/O-efficient algorithms for graphs of bounded treewidth, Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, On the complexity of constrained Nash equilibria in graphical games, Computing directed pathwidth in \(O(1.89^n)\) time, Approximate tree decompositions of planar graphs in linear time, Constraint satisfaction with bounded treewidth revisited, Collective tree spanners in graphs with bounded parameters, Approximation algorithms for treewidth, Coloring immersion-free graphs, Differential geometric treewidth estimation in adiabatic quantum computation, Model counting for CNF formulas of bounded modular treewidth, Parameterized complexity of the \(k\)-arc Chinese postman problem, Kernelization using structural parameters on sparse graph classes, Online promise problems with online width metrics, The parameterised complexity of list problems on graphs of bounded treewidth, Treewidth and pathwidth parameterized by the vertex cover number, Irrelevant vertices for the planar disjoint paths problem, Courcelle's theorem for triangulations, The minimum vulnerability problem on specific graph classes, Matching interdiction, Some recent progress and applications in graph minor theory, Achievable sets, brambles, and sparse treewidth obstructions, Increasing the minimum degree of a graph by contractions, Incremental list coloring of graphs, parameterized by conservation, Kernel bounds for path and cycle problems, Tree projections and structural decomposition methods: minimality and game-theoretic characterization, Parameterized complexity of connected even/odd subgraph problems, Optimal cuts and partitions in tree metrics in polynomial time, Optimization problems in dotted interval graphs, Complexity of finding maximum regular induced subgraphs with prescribed degree, Courcelle's theorem -- a game-theoretic approach, Weighted maximum-clique transversal sets of graphs, The most vital nodes with respect to independent set and vertex cover, The disjoint paths problem in quadratic time, The complexity of two graph orientation problems, The complexity of minimum convex coloring, Compact labelings for efficient first-order model-checking, Approximation of minimum weight spanners for sparse graphs, Linkless and flat embeddings in 3-space, On shortest disjoint paths in planar graphs, Fast evaluation of interlace polynomials on graphs of bounded treewidth, Contracting planar graphs to contractions of triangulations, Acyclic and star colorings of cographs, The complexity of finding uniform sparsest cuts in various graph classes, Treewidth governs the complexity of target set selection, On the complexity of core, kernel, and bargaining set, Guard games on graphs: keep the intruder out!, Guarantees and limits of preprocessing in constraint satisfaction and reasoning, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, Confronting intractability via parameters, Algorithms for finding an induced cycle in planar graphs, Compact navigation and distance oracles for graphs with small treewidth, Practical algorithms for MSO model-checking on tree-decomposable graphs, Spanners in sparse graphs, Approximation algorithms for intersection graphs, Computing the pathwidth of directed graphs with small vertex cover, Consequence-based and fixed-parameter tractable reasoning in description logics, The complexity of minimum-length path decompositions, \(k\)-chordal graphs: from cops and robber to compact routing via treewidth, Fixed-parameter algorithms for DAG partitioning, Squares of low clique number, Parameterized complexity of critical node cuts, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, MSOL restricted contractibility to planar graphs, Efficient computation of the characteristic polynomial of a tree and related tasks, On making a distinguished vertex of minimum degree by vertex deletion, FPT algorithms for connected feedback vertex set, Hypertree decompositions and tractable queries, Treewidth computations. II. Lower bounds, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Girth and treewidth, Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree, Upper and lower bounds for finding connected motifs in vertex-colored graphs, Complexity of secure sets, Well-quasi-ordering versus clique-width: new results on bigenic classes, Finding cactus roots in polynomial time, Nonempty intersection of longest paths in series-parallel graphs, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, The complexity ecology of parameters: An illustration using bounded max leaf number, A linear edge kernel for two-layer crossing minimization, Connecting knowledge compilation classes and width parameters, On the complexity of reasoning about opinion diffusion under majority dynamics, Complexity of abstract argumentation under a claim-centric view, A faster tree-decomposition based algorithm for counting linear extensions, Exact algorithms for intervalizing coloured graphs, Improved approximation for orienting mixed graphs, Equitable colorings of bounded treewidth graphs, The longest common subsequence problem for sequences with nested arc annotations., Treewidth of the generalized Kneser graphs, The parametrized complexity of knot polynomials, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, A polynomial time algorithm for strong edge coloring of partial \(k\)-trees, An existential locality theorem, Computing crossing numbers in quadratic time, Safe sets in graphs: graph classes and structural parameters, Treewidth distance on phylogenetic trees, An analysis of the parameterized complexity of periodic timetabling, Minimum \(t\)-spanners on subcubic graphs, Treewidth for graphs with small chordality, On interval routing schemes and treewidth, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, MSOL partitioning problems on graphs of bounded treewidth and clique-width, Improved Steiner tree algorithms for bounded treewidth, Structure and algorithms for (cap, even hole)-free graphs, Recoloring graphs via tree decompositions, Binary jumbled pattern matching on trees and tree-like structures, Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams, Practical algorithms for branch-decompositions of planar graphs, A faster parameterized algorithm for pseudoforest deletion, Spanners of bounded degree graphs, The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs, Splitting a graph into disjoint induced paths or cycles., An FPT 2-approximation for tree-cut decomposition, Matchings with lower quotas: algorithms and complexity, A new ant colony optimization algorithm for the lower bound of sum coloring problem, Parameterized algorithms for stable matching with ties and incomplete lists, Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs, Constrained-path labellings on graphs of bounded clique-width, Treewidth lower bounds with brambles, Maximum \(k\)-splittable \(s, t\)-flows, Turbocharging treewidth heuristics, Clifford algebras meet tree decompositions, Cutwidth: obstructions and algorithmic aspects, Three-connected graphs whose maximum nullity is at most three, An annotated bibliography on guaranteed graph searching, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, A gentle introduction to applications of algorithmic metatheorems for space and circuit classes, Explicit linear kernels for packing problems, Counting linear extensions: parameterizations by treewidth, A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter, Polynomial bounds for centered colorings on proper minor-closed graph classes, Crossing number for graphs with bounded pathwidth, On the complexity of computing treebreadth, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, Fly-automata for checking \(\mathrm{MSO}_2\) graph properties, On the parameterized complexity of layered graph drawing, Treewidth computations. I: Upper bounds, Parameterized complexity of the spanning tree congestion problem, Towards fixed-parameter tractable algorithms for abstract argumentation, Practical access to dynamic programming on tree decompositions, A cubic kernel for feedback vertex set and loop cutset, Two feedback problems for graphs with bounded tree-width, Tree decompositions with small cost, Embeddings of \(k\)-connected graphs of pathwidth \(k\), Computing the branchwidth of interval graphs, On the complexity of computing treelength, Querying linguistic treebanks with monadic second-order logic in linear time, Efficient frequent connected subgraph mining in graphs of bounded tree-width, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, On structural parameterizations of the edge disjoint paths problem, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Some tractable instances of interval data minmax regret problems, On \textsf{NC} algorithms for problems on bounded rank-width graphs, Treewidth and logical definability of graph products, On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines, Complete-subgraph-transversal-sets problem on bounded treewidth graphs, Confluence up to garbage in graph transformation, A spectral lower bound for the treewidth of a graph and its consequences, Derivation of algorithms for cutwidth and related graph layout parameters, Parameterized complexity of vertex colouring, Optimal tree decompositions revisited: a simpler linear-time FPT algorithm, All structured programs have small tree width and good register allocation, Upper and lower degree-constrained graph orientation with minimum penalty, Efficient Union-Find for planar graphs and other sparse graph classes, The parameterized complexity of the induced matching problem, Computational properties of argument systems satisfying graph-theoretic constraints, Characterizing multiterminal flow networks and computing flows in networks of small treewidth, On problems without polynomial kernels, Orthogonal planarity testing of bounded treewidth graphs, Chordal bipartite graphs of bounded tree- and clique-width, Algorithms for generalized vertex-rankings of partial k-trees, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, Fast and parallel decomposition of constraint satisfaction problems, Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth, Algorithms and obstructions for linear-width and related search parameters, An algorithm for the Tutte polynomials of graphs of bounded treewidth, Measuring power in coalitional games with friends, enemies and allies, Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size, Maximum likelihood bounded tree-width Markov networks, Reduction algorithms for graphs of small treewidth, The complexity of the \(K_{n,n}\)-problem for node replacement graph languages, Counting \(H-\)colorings of partial \(k-\)trees, Fixed-parameter complexity in AI and nonmonotonic reasoning, Listing all potential maximal cliques of a graph, An implementation of the iterative proportional fitting procedure by propagation trees., Parameterized complexity of \((A,\ell)\)-path packing, Parameterized Complexity of $$(A,\ell )$$-Path Packing, Parameterized Complexity of Firefighting Revisited, Increasing the Minimum Degree of a Graph by Contractions, Finding Good Decompositions for Dynamic Programming on Dense Graphs, Algorithms, Complexity, and Hans, As Time Goes By: Reflections on Treewidth for Temporal Graphs, A Survey on Spanning Tree Congestion, Computing Tree Decompositions, Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel, Linear Time Parameterized Algorithms for Subset Feedback Vertex Set, An Improvement of Reed’s Treewidth Approximation, Towards the Graph Minor Theorems for Directed Graphs, Provenance Circuits for Trees and Treelike Instances, Containment of Monadic Datalog Programs via Bounded Clique-Width, Kernelization of Cycle Packing with Relaxed Disjointness Constraints, Subexponential Time Algorithms for Finding Small Tree and Path Decompositions, A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity, On the Pathwidth of Almost Semicomplete Digraphs, Community Structure Inspired Algorithms for SAT and #SAT, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, Constructing Brambles, On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), Approximation of the Quadratic Knapsack Problem, Graphical Models and Message-Passing Algorithms: Some Introductory Lectures, Unnamed Item, Unnamed Item, A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs, Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth, Constructive linear time algorithms for branchwidth, Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem, The Minimum Vulnerability Problem on Graphs, Connecting Width and Structure in Knowledge Compilation (Extended Version), Improved Parameterized Algorithms for Network Query Problems, Deterministic Algorithms for the Independent Feedback Vertex Set Problem, Algorithms for Propositional Model Counting, The power of non-ground rules in Answer Set Programming, An Improved Algorithm for Finding Cycles Through Elements, Safe Sets in Graphs: Graph Classes and Structural Parameters, Efficient First-Order Model-Checking Using Short Labels, Parameterized complexity of computing maximum minimal blocking and hitting sets, Obtaining a Planar Graph by Vertex Deletion, Grid induced minor theorem for graphs of small degree, Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth, Unnamed Item, Unnamed Item, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs, Parameterized study of Steiner tree on unit disk graphs, Typical sequences revisited -- computing width parameters of graphs, Fair allocation of indivisible items with conflict graphs, An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths, On the Maximum Weight Minimal Separator, Unnamed Item, The Complexity Status of Problems Related to Sparsest Cuts, Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures, Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$, Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width, Practical Access to Dynamic Programming on Tree Decompositions, A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions, How to Cut a Graph into Many Pieces, Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization, APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM, The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey, Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Monadic Second Order Logic on Graphs with Local Cardinality Constraints, Complexity Results for the Spanning Tree Congestion Problem, Hitting Forbidden Minors: Approximation and Kernelization, A $c^k n$ 5-Approximation Algorithm for Treewidth, A Local Search Algorithm for Branchwidth, On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision, Half-integrality, LP-branching, and FPT Algorithms, Equitable list coloring and treewidth, On the Complexity of Computing Treebreadth, Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes, Finding Cactus Roots in Polynomial Time, Faster Computation of Path-Width, Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics, How to Secure Matchings Against Edge Failures, An Experimental Study of the Treewidth of Real-World Graph Data, Tree-Width for First Order Formulae, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Completing Networks Using Observed Data, Integrating and Sampling Cuts in Bounded Treewidth Graphs, A Polynomial Time Algorithm for Bounded Directed Pathwidth, The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth, The complexity of the matching-cut problem for planar graphs and other graph classes, Tree Projections: Game Characterization and Computational Aspects, Dynamic algorithms for graphs of bounded treewidth, Minimizing the Oriented Diameter of a Planar Graph, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Augmenting Outerplanar Graphs to Meet Diameter Requirements, Unnamed Item, Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs, Graph decompositions for cartesian products, Myhill-Nerode Methods for Hypergraphs, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, Degree-constrained decompositions of graphs: Bounded treewidth and planarity, Tree-decompositions with bags of small diameter, Efficient algorithms for center problems in cactus networks, Characteristic function games with restricted agent interactions: core-stability and coalition structures, Fixed-parameter approximation: conceptual framework and approximability results, Spanners for bounded tree-length graphs, Boxicity and treewidth, The relative clique-width of a graph, Treewidth computation and extremal combinatorics, Structural parameterizations with modulator oblivion, Space-efficient vertex separators for treewidth, Boundary classes for graph problems involving non-local properties, A linear kernel for finding square roots of almost planar graphs, Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs, The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing, The tree-width of C, Hitting forbidden subgraphs in graphs of bounded treewidth, Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability, Lpopt: a rule optimization tool for answer set programming, On the vertex cover \(P_3\) problem parameterized by treewidth, An approval-based model for single-step liquid democracy, Parameterized extension complexity of independent set and related problems, Computing square roots of graphs with low maximum degree, FPT algorithms to compute the elimination distance to bipartite graphs and more, Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges, The graphs of stably matchable pairs, Improved parameterized algorithms for network query problems, The connected critical node problem, Solving projected model counting by utilizing treewidth and its limits, Parameterized complexity of envy-free resource allocation in social networks, Host-graph-sensitive RETE nets for incremental graph pattern matching with nested graph conditions, Positive-instance driven dynamic programming for treewidth, Obtaining a planar graph by vertex deletion, Minimize the maximum duty in multi-interface networks, Tractable cases of the extended global cardinality constraint, Polynomial kernels for hitting forbidden minors under structural parameterizations, Scheduling of pipelined operator graphs, Structural parameters for scheduling with assignment restrictions, Bundled crossings revisited, Sketched representations and orthogonal planarity of bounded treewidth graphs, Fixed-parameter algorithms for the cocoloring problem, Coloring graphs without short cycles and long induced paths, Digraphs of bounded elimination width, Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth, Imbalance is fixed parameter tractable, A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number, Graphs whose complement and square are isomorphic, How to compute digraph width measures on directed co-graphs, Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm, Parameterized complexity of firefighting, Branch-depth: generalizing tree-depth of graphs, Adiabatic quantum programming: minor embedding with hard faults, Algorithms for finding distance-edge-colorings of graphs, Weighted total acquisition, Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes, An improvement of Reed's treewidth approximation, Case-factor diagrams for structured probabilistic modeling, Visualizing SAT instances and runs of the DPLL algorithm, Discrete optimization methods for group model selection in compressed sensing, Frameworks for designing in-place graph algorithms, Refined notions of parameterized enumeration kernels with applications to matching cut enumeration, New width parameters for SAT and \#SAT, On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon, Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem, On the complexity of connectivity in cognitive radio networks through spectrum assignment, Tree decomposition and discrete optimization problems: a survey, On the complexity of the identifiable subgraph problem, Planar graph bipartization in linear time, Kernels in planar digraphs, An exact method for graph coloring, On the colored Tutte polynomial of a graph of bounded treewidth, Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees, Algorithms for propositional model counting, Bounded treewidth as a key to tractability of knowledge representation and reasoning, On the parameterized complexity of the geodesic hull number, Improved bottleneck domination algorithms, Characterization of graphs and digraphs with small process numbers, Treewidth, crushing and hyperbolic volume, Assortment optimization under the multinomial logit model with product synergies, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, Using decomposition-parameters for QBF: mind the prefix!, Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth, Algorithms and complexity for Turaev-Viro invariants, Deleting vertices to graphs of bounded genus, Cooperative games with overlapping coalitions: charting the tractability frontier, Evaluating Datalog via tree automata and cycluits, Finding small-width connected path decompositions in polynomial time, The recognizability of sets of graphs is a robust property, Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth, On the maximum weight minimal separator, Finding, hitting and packing cycles in subexponential time on unit disk graphs, The complexity of finding harmless individuals in social networks, Parameterized computation and complexity: a new approach dealing with NP-hardness, Methods for solving reasoning problems in abstract argumentation -- a survey, Pure Nash equilibria in graphical games and treewidth, Constructing NP-intermediate problems by blowing holes with parameters of various properties, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree, On maximum independent set of categorical product and ultimate categorical ratios of graphs, A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
