Directed tree-width

DOI10.1006/jctb.2000.2031zbMath1027.05045OpenAlexW2054167510MaRDI QIDQ1850539

Neil Robertson, Thor Johnson, Robin Thomas, P. D. Seymour

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/694eae37f0b88804b3a2355b800b0acac7b31cf4

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items

Strong complete minors in digraphs, Characterizations and directed path-width of sequence digraphs, Complete directed minors and chromatic number, Spined categories: generalizing tree-width beyond graphs, Cut-sufficient directed 2-commodity multiflow topologies, Excluding a planar matching minor in bipartite graphs, Unnamed Item, Classes of intersection digraphs with good algorithmic properties, Efficient algorithms for measuring the funnel-likeness of DAGs, Undirected Graphs of Entanglement 2, Unnamed Item, Leafy spanning arborescences in DAGs, An algorithmic metatheorem for directed treewidth, Computing the zig-zag number of directed graphs, Adapting the directed grid theorem into an \textsf{FPT} algorithm, On the monotonicity of process number, Towards the Graph Minor Theorems for Directed Graphs, Computing directed pathwidth in \(O(1.89^n)\) time, Even circuits in oriented matroids, What’s Next? Future Directions in Parameterized Complexity, ON MODAL μ-CALCULUS OVER FINITE GRAPHS WITH SMALL COMPONENTS OR SMALL TREE WIDTH, Digraph Decompositions and Monotonicity in Digraph Searching, Directed width parameters on semicomplete digraphs, Directed tree-width examples, Directed Pathwidth and Palletizers, Constant Congestion Brambles in Directed Graphs, Jumping robbers in digraphs, DAG-width is PSPACE-complete, Eccentricity queries and beyond using hub labels, Recent techniques and results on the Erdős-Pósa property, Disjoint Cycles with Length Constraints in Digraphs of Large Connectivity or Large Minimum Degree, A cops and robber game in multidimensional grids, Some recent progress and applications in graph minor theory, Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, Entanglement and the complexity of directed graphs, Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs, Adapting the Directed Grid Theorem into an FPT Algorithm, Are there any good digraph width measures?, The all-or-nothing flow problem in directed graphs with symmetric demand pairs, Directed elimination games, Monotonicity of Non-deterministic Graph Searching, Characterization and Recognition of Digraphs of Bounded Kelly-width, Monotonicity of strong searching on digraphs, Unnamed Item, Directed NLC-width, Graph theory. Abstracts from the workshop held January 2--8, 2022, Finite Automata, Digraph Connectivity, and Regular Expression Size, Digraph decompositions and monotonicity in digraph searching, The dag-width of directed graphs, Digraphs of bounded elimination width, Digraph width measures in parameterized algorithmics, An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths, On the algorithmic effectiveness of digraph decompositions and complexity measures, Solutions for subset sum problems with special digraph constraints, How to compute digraph width measures on directed co-graphs, Monotonicity of non-deterministic graph searching, Digraph measures: Kelly decompositions, games, and orderings, An annotated bibliography on guaranteed graph searching, Finding a subdivision of a digraph, Approximation algorithms for digraph width parameters, On directed covering and domination problems, Digraph searching, directed vertex separation and directed pathwidth, On the complexity of the multicut problem in bounded tree-width graphs and digraphs, An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents, Forbidden directed minors and Kelly-width, Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials, Monotonicity in digraph search problems, An extended tree-width notion for directed graphs related to the computation of permanents, Oriented coloring on recursively defined digraphs, Towards fixed-parameter tractable algorithms for abstract argumentation, On complexity of minimum leaf out-branching problem, Digraphs of directed treewidth one, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, A trichotomy for regular simple path queries on graphs, Recognizing digraphs of Kelly-width 2, Unnamed Item, The treewidth of proofs, LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth, Half-integral linkages in highly connected directed graphs, Routing with congestion in acyclic digraphs, Unnamed Item, Directed path-width and monotonicity in digraph searching, On the hardness of finding near-optimal multicuts in directed acyclic graphs, On characterizations for subclasses of directed co-graphs, Are There Any Good Digraph Width Measures?, Excluding a bipartite circle graph from line graphs, Directed width parameters and circumference of digraphs, Algorithms for Controlling Palletizers, DAG-Width and Circumference of Digraphs, Directed Path-Decompositions, LIFO-Search on Digraphs: A Searching Game for Cycle-Rank, A relaxation of the directed disjoint paths problem: a global congestion metric helps, A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps., Tight Bounds on the Descriptional Complexity of Regular Expressions, A Slice Theoretic Approach for Embedding Problems on Digraphs, On width measures and topological problems on semi-complete digraphs, Standard directed search strategies and their applications, A Polynomial Time Algorithm for Bounded Directed Pathwidth, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, Comparing linear width parameters for directed graphs, On Digraph Width Measures in Parameterized Algorithmics, Tournaments and Semicomplete Digraphs, Euler Digraphs, Planar Digraphs, Digraphs of Bounded Width, Well-quasi-ordering hereditarily finite sets, Tournament minors, On Directed Covering and Domination Problems, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, Disjoint Paths in Decomposable Digraphs, On the complexity of the FIFO stack-up problem

Cites Work