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 (only showing first 100 items - show all)

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

This page was built for publication: