scientific article; zbMATH DE number 566078

Publication date: 12 January 1995

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

bibliography treewidth graph minor pathwidth algorithmic graph theory tree-decompositions

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Bibliographies for mathematics in general (00A15)

Related Items

Seeing Arboretum for the (partial k-) Trees, As Time Goes By: Reflections on Treewidth for Temporal Graphs, Fast Algorithms for Join Operations on Tree Decompositions, Some notes on bounded starwidth graphs, Memory requirements for table computations in partial k-tree algorithms, On the k-rainbow domination in graphs with bounded tree-width, Graphical Models and Message-Passing Algorithms: Some Introductory Lectures, Boxicity and treewidth, The stable set problem and the thinness of a graph, Semiring induced valuation algebras: exact and approximate local computation algorithms, Unnamed Item, Directed Pathwidth and Palletizers, Unnamed Item, On the pathwidth of hyperbolic 3-manifolds, Graph Bisection with Pareto Optimization, On strictly chordality-\(k\) graphs, Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets, Bounding the Clique-Width of H-free Chordal Graphs, Algorithms for Propositional Model Counting, Independent set under a change constraint from an initial solution, Approximating Pathwidth for Graphs of Small Treewidth, Complexity and Algorithms for Well-Structured k-SAT Instances, Monoidal Width, The complexity of learning minor closed graph classes, Galactic token sliding, Optimal parallel shortest paths in small treewidth digraphs, Shallow Minors, Graph Products, and Beyond-Planar Graphs, How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms, Isoperimetric Problem and Meta-fibonacci Sequences, Efficient interprocedural data-flow analysis using treedepth and treewidth, Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint, Treewidth of the \(q\)-Kneser graphs, Domino treewidth, A lower bound for treewidth and its consequences, Tree-width and path-width of comparability graphs of interval orders, Dominoes, Rankings of graphs, On reduction algorithms for graphs with small treewidth, Reduction algorithms for constructing solutions in graphs with small treewidth, Tractable cases of the extended global cardinality constraint, Locating Eigenvalues of Symmetric Matrices - A Survey, On structural parameterizations of Node Kayles, On treewidth, separators and Yao's garbling, The theory of guaranteed search on graphs, Parameters Tied to Treewidth, Digraph width measures in parameterized algorithmics, Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs, Counting solutions to CSP using generating polynomials, Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm, The “Art of Trellis Decoding” Is NP-Hard, Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree, Tight bounds for online coloring of basic graph classes, Treewidth and pathwidth of permutation graphs, Adiabatic quantum programming: minor embedding with hard faults, Vertex-minor reductions can simulate edge contractions, Parameterized Leaf Power Recognition via Embedding into Graph Products, New width parameters for SAT and \#SAT, How to use the minimal separators of a graph for its chordal triangulation, Shortest path queries in digraphs of small treewidth, Tight Bounds for Linkages in Planar Graphs, Compact Navigation and Distance Oracles for Graphs with Small Treewidth, On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon, Fugitive-search games on graphs and related parameters, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Tree decomposition and discrete optimization problems: a survey, A Practical Approach to Courcelle's Theorem, The pagenumber of \(k\)-trees is \(O(k)\), An exact method for graph coloring, Branch-width, parse trees, and monadic second-order logic for matroids., Algorithms for propositional model counting, Lower bounds for strictly fundamental cycle bases in grid graphs, Unnamed Item, Parameterized shifted combinatorial optimization, Linear ordering based MIP formulations for the vertex separation or pathwidth problem, Unnamed Item, On recognizing graphs by numbers of homomorphisms, selp: A Single-Shot Epistemic Logic Program Solver, Parameterised complexity of model checking and satisfiability in propositional dependence logic, Walking through waypoints, Unnamed Item, An Efficient Partitioning Oracle for Bounded-Treewidth Graphs, Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited, Limit Set Reachability in Asynchronous Graph Dynamical Systems, Treewidth of display graphs: bounds, brambles and applications, The complexity of the matching-cut problem for planar graphs and other graph classes, Tight Bounds for Online Coloring of Basic Graph Classes, On the Tree-Width of Planar Graphs, Tree decompositions and social graphs, The height of random k‐trees and related branching processes, Backdoors to tractable answer set programming, Unnamed Item, Unnamed Item, On Advice Complexity of the k-server Problem under Sparse Metrics, Customizable Contraction Hierarchies, The treewidth of 2-section of hypergraphs, Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results, Perfect edge domination and efficient edge domination in graphs, Improving robustness of next-hop routing, Minimal triangulations of graphs: a survey, Compatibility of unrooted phylogenetic trees is FPT, Treewidth of the generalized Kneser graphs, A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Treewidth of cocomparability graphs and a new order-theoretic parameter, Computing directed pathwidth in \(O(1.89^n)\) time, Approximate tree decompositions of planar graphs in linear time, Reduction rules for the maximum parsimony distance on phylogenetic trees, Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases, Treewidth distance on phylogenetic trees, Complexity of list coloring problems with a fixed total number of colors, Geometric representation of graphs in low dimension using axis parallel boxes, Matroid tree-width, A parameterized view on the complexity of dependence logic, Complexity of reachability problems for finite discrete dynamical systems, Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane, Treewidth for graphs with small chordality, Characterizations and algorithmic applications of chordal graph embeddings, Triangulating graphs without asteroidal triples, \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling], Pushdown reachability with constant treewidth, Secluded connectivity problems, MSOL partitioning problems on graphs of bounded treewidth and clique-width, Fugitive-search games on graphs and related parameters, On treewidth and minimum fill-in of asteroidal triple-free graphs, Triangulating multitolerance graphs, Improved Steiner tree algorithms for bounded treewidth, Reconfiguration in bounded bandwidth and tree-depth, Optimization problems in dotted interval graphs, Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs, Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem, Courcelle's theorem -- a game-theoretic approach, A new probabilistic constraint logic programming language based on a generalised distribution semantics, Practical algorithms for branch-decompositions of planar graphs, The complexity of two graph orientation problems, Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs, Enumerating homomorphisms, Polynomial-time recognition of clique-width \(\leq 3\) graphs, Scale free properties of random \(k\)-trees, On the complexity of some colorful problems parameterized by treewidth, The multi-stripe travelling salesman problem, Minesweeper on graphs, Matchings with lower quotas: algorithms and complexity, Satisfiability, branch-width and Tseitin tautologies, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, Algorithms and complexity results for persuasive argumentation, Treewidth governs the complexity of target set selection, Subexponential parameterized algorithms, The obnoxious center problem on weighted cactus graphs., Compact navigation and distance oracles for graphs with small treewidth, Practical algorithms for MSO model-checking on tree-decomposable graphs, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs, A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization, A simple linear-time algorithm for finding path-decompositions of small width, On the advice complexity of the \(k\)-server problem under sparse metrics, On the path-width of integer linear programming, The critical node detection problem in networks: a survey, Parameterized complexity of critical node cuts, Complexity of Grundy coloring and its variants, Toughness threshold for the existence of 2-walks in \(K_{4}\)-minor-free graphs, Sex-equal stable matchings: complexity and exact algorithms, Treewidth computations. I: Upper bounds, On the complexity of some subgraph problems, A graph search algorithm for indoor pursuit/evasion, Bijective linear time coding and decoding for \(k\)-trees, Independence polynomials of \(k\)-tree related graphs, Dynamic programming and planarity: improved tree-decomposition based algorithms, The Steiner forest problem revisited, Chordal deletion is fixed-parameter tractable, A little statistical mechanics for the graph theorist, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Girth and treewidth, Querying linguistic treebanks with monadic second-order logic in linear time, Efficient frequent connected subgraph mining in graphs of bounded tree-width, Upper and lower bounds for finding connected motifs in vertex-colored graphs, Comparing universal covers in polynomial time, Complexity of secure sets, The treewidth of line graphs, Combinatorial properties of a general domination problem with parity constraints, Bounds on isoperimetric values of trees, A spectral lower bound for the treewidth of a graph and its consequences, Faster algorithms for quantitative verification in bounded treewidth graphs, Notes on graph product structure theory, On two techniques of combining branching and treewidth, All structured programs have small tree width and good register allocation, Efficient Union-Find for planar graphs and other sparse graph classes, Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms, A partial k-arboretum of graphs with bounded treewidth, Complexity results for minimum sum edge coloring, A survey on interval routing, On spanning tree congestion of graphs, Parameterized leaf power recognition via embedding into graph products, An algorithm for the Tutte polynomials of graphs of bounded treewidth, Listing all potential maximal cliques of a graph, A generic convolution algorithm for join operations on tree decompositions, On the complexity of the FIFO stack-up problem