Graph minors. III. Planar tree-width
From MaRDI portal
Publication:799684
DOI10.1016/0095-8956(84)90013-3zbMath0548.05025OpenAlexW2002722727WikidataQ56141697 ScholiaQ56141697MaRDI QIDQ799684
Publication date: 1984
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(84)90013-3
Related Items
Treewidth of the generalized Kneser graphs, A new approach on locally checkable problems, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Improved self-reduction algorithms for graphs with bounded treewidth, The balanced satisfactory partition problem, A polynomial time algorithm to compute the connected treewidth of a series-parallel graph, Even-power of cycles with many vertices are type 1 total colorable, An existential locality theorem, Datalog vs first-order logic, Parameterized dominating set problem in chordal graphs: Complexity and lower bound, Posets with cover graph of pathwidth two have bounded dimension, Approximate tree decompositions of planar graphs in linear time, Deleting edges to restrict the size of an epidemic: a new application for treewidth, On the complexity of connection games, An analysis of the parameterized complexity of periodic timetabling, Grids and their minors, Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case, A parameterized view on the complexity of dependence logic, On embedding graphs in trees, On the harmless set problem parameterized by treewidth, Graph minors. VII: Disjoint paths on a surface, On tree-partitions of graphs, Treewidth for graphs with small chordality, The Menger-like property of the three-width of infinite graphs, The tree-width of C, Some recent progress and applications in graph minor theory, Pushdown reachability with constant treewidth, Log-space algorithms for paths and matchings in \(k\)-trees, The density maximization problem in graphs, Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}, Entanglement and the complexity of directed graphs, Hypertree-depth and minors in hypergraphs, Tree projections and structural decomposition methods: minimality and game-theoretic characterization, Fugitive-search games on graphs and related parameters, Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs, Improved bounds on the planar branchwidth with respect to the largest grid minor size, Combinatorial problems on \(H\)-graphs, Tree-chromatic number, Sublinear separators, fragility and subexponential expansion, On self-duality of branchwidth in graphs of bounded genus, The complexity of two graph orientation problems, Interdiction problems on planar graphs, Tree-width of hypergraphs and surface duality, Approximation of minimum weight spanners for sparse graphs, Bounds for mean colour numbers of graphs, Constant-degree graph expansions that preserve treewidth, An FPT 2-approximation for tree-cut decomposition, On fractional fragility rates of graph classes, The P3 infection time is W[1-hard parameterized by the treewidth], A short note on the complexity of computing strong pathbreadth, Multidimensional bipartite trees, The dag-width of directed graphs, Chordal embeddings of planar graphs, Distance labeling scheme and split decomposition, On the complexity of core, kernel, and bargaining set, Clifford algebras meet tree decompositions, Complexity of semi-stable and stage semantics in argumentation frameworks, On the hyperbolicity constant in graph minors, Consequence-based and fixed-parameter tractable reasoning in description logics, \(k\)-chordal graphs: from cops and robber to compact routing via treewidth, Efficiently enumerating minimal triangulations, On the advice complexity of the \(k\)-server problem under sparse metrics, A characterization of some graph classes using excluded minors, Lower bounds for positive semidefinite zero forcing and their applications, On classes of graphs with strongly sublinear separators, On compatibility and incompatibility of collections of unrooted phylogenetic trees, Partitions versus sets: a case of duality, Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time, A little statistical mechanics for the graph theorist, Interval routing in reliability networks, Succinct monotone circuit certification: planarity and parameterized complexity, Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree, On the complexity of embedding planar graphs to minimize certain distance measures, Complexity of secure sets, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Complete-subgraph-transversal-sets problem on bounded treewidth graphs, 2-connecting outerplanar graphs without blowing up the pathwidth, Universal augmentation schemes for network navigability, Graph minors. IX: Disjoint crossed paths, Faster algorithms for quantitative verification in bounded treewidth graphs, Upper and lower degree-constrained graph orientation with minimum penalty, Linear connectivity forces large complete bipartite minors, A partial k-arboretum of graphs with bounded treewidth, Nested cycles in large triangulations and crossing-critical graphs, Multiplicities of eigenvalues and tree-width of graphs, Excluding any graph as a minor allows a low tree-width 2-coloring, On the scramble number of graphs, Defensive alliances in graphs, On the complexity of reasoning about opinion diffusion under majority dynamics, Compositions, decompositions, and conformability for total coloring on power of cycle graphs, Graph minors. I. Excluding a forest, Surfaces, tree-width, clique-minors, and partitions, Directed tree-width, Graphs with magnetic Schrödinger operators of low corank, A meta-theorem for distributed certification, Counting \(H-\)colorings of partial \(k-\)trees, The structure of the models of decidable monadic theories of graphs, Listing all potential maximal cliques of a graph, New limits of treewidth-based tractability in optimization, On preprocessing techniques and their impact on propositional model counting, Finite reflection groups and graph norms, A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings, Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, On the complexity of the disjoint paths problem, Rank-width of random graphs, Simple monadic theories and partition width, Efficient Problem Solving on Tree Decompositions Using Binary Decision Diagrams, An Improvement of Reed’s Treewidth Approximation, Positive Semidefinite Zero Forcing: Complexity and Lower Bounds, Weighted proper orientations of trees and graphs of bounded treewidth, Sequential and parallel algorithms for embedding problems on classes of partial k-trees, Characteristic function games with restricted agent interactions: core-stability and coalition structures, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, ON MODAL μ-CALCULUS OVER FINITE GRAPHS WITH SMALL COMPONENTS OR SMALL TREE WIDTH, Mixed covering arrays on graphs of small treewidth, Graph minors. IV: Tree-width and well-quasi-ordering, Graph minors. VIII: A Kuratowski theorem for general surfaces, Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth, On the Satisfiability of Quantum Circuits of Small Treewidth, Maximum flow under proportional delay constraint, Answering conjunctive queries with inequalities, Properties of Large 2-Crossing-Critical Graphs, Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs, Helly-gap of a graph and vertex eccentricities, Dichotomies properties on computational complexity of \(S\)-packing coloring problems, Layered separators in minor-closed graph classes with applications, The \(k\)-strong induced arboricity of a graph, Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability, On the satisfiability of quantum circuits of small treewidth, Globally minimal defensive alliances, Compact representation of graphs with bounded bandwidth or treedepth, A Note on the Minimum H-Subgraph Edge Deletion, Computing the best-case energy complexity of satisfying assignments in monotone circuits, Algebras for Tree Decomposable Graphs, Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem, Large Induced Subgraphs via Triangulations and CMSO, \(K_{6}\) minors in 6-connected graphs of bounded tree-width, Host-graph-sensitive RETE nets for incremental graph pattern matching with nested graph conditions, On Strong Tree-Breadth, The mixed search game against an agile and visible fugitive is monotone, On strict brambles, Unnamed Item, Sublinear-space approximation algorithms for Max \(r\)-SAT, Perfectly matched sets in graphs: parameterized and exact computation, Maximizing ink in partial edge drawings of \(k\)-plane graphs, The theory of guaranteed search on graphs, Fixed-parameter algorithms for the cocoloring problem, On the complexity of planning for agent teams and its implications for single agent planning, Beyond Outerplanarity, Burning Two Worlds, An improvement of Reed's treewidth approximation, How to Navigate Through Obstacles, The Small Set Vertex expansion problem, Succinct certification of monotone circuits, LP Formulations for Polynomial Optimization Problems, On Algorithms Employing Treewidth for $L$-bounded Cut Problems, Coloring temporal graphs, D-FLAT: Declarative problem solving using tree decompositions and answer-set programming, Tree decomposition and discrete optimization problems: a survey, Unnamed Item, On the colored Tutte polynomial of a graph of bounded treewidth, On the parameterized complexity of the geodesic hull number, Excluding Subdivisions of Infinite Cliques, Unnamed Item, A model-theoretic characterisation of clique width, Unnamed Item, Two approaches to Sidorenko’s conjecture, Decompositions of Triangle-Dense Graphs, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Classical spin systems and the quantum stabilizer formalism: General mappings and applications, Towards a characterization of order-invariant queries over tame graphs, Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value, Graph minor theory, Approximation algorithms for connected maximum cut and related problems, Computational aspects of optimal strategic network diffusion, An Efficient Partitioning Oracle for Bounded-Treewidth Graphs, Bidimensionality and Kernels, An Experimental Study of the Treewidth of Real-World Graph Data, Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth., Finding Hamiltonian Cycle in Graphs of Bounded Treewidth, Integrating and Sampling Cuts in Bounded Treewidth Graphs, A Polynomial Time Algorithm for Bounded Directed Pathwidth, Positive semidefinite zero forcing numbers of two classes of graphs, Cooperative games with overlapping coalitions: charting the tractability frontier, Tree-width of graphs and surface duality, Evaluating Datalog via tree automata and cycluits, Tree Projections: Game Characterization and Computational Aspects, Kernelization: New Upper and Lower Bound Techniques, Minimizing the Oriented Diameter of a Planar Graph, Methods for solving reasoning problems in abstract argumentation -- a survey, Backdoors to tractable answer set programming, Structural tractability of enumerating CSP solutions, Unnamed Item, Treewidth of planar graphs: connections with duality, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, On maximum independent set of categorical product and ultimate categorical ratios of graphs, The treewidth of 2-section of hypergraphs, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, Self-avoiding walks and multiple context-free languages, Clustered 3-colouring graphs of bounded degree, On tripartite common graphs, The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Unnamed Item, Constant Congestion Brambles, Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs, Edge-treewidth: algorithmic and combinatorial properties, On some graph densities in locally dense graphs, Generating random instances of weighted model counting. An empirical analysis with varying primal treewidth, Linear‐time algorithms for eliminating claws in graphs, The complexity of learning minor closed graph classes, Parameterized intractability of defensive alliance problem, Branchwidth is \((1, g)\)-self-dual, Treewidth versus clique number. II: Tree-independence number, Solving infinite-domain CSPs using the patchwork property, Allocation of indivisible items with individual preference graphs, Efficient interprocedural data-flow analysis using treedepth and treewidth, Treewidth of the \(q\)-Kneser graphs, Characterizing and generalizing cycle completable graphs, Treewidth, Circle Graphs, and Circular Drawings, Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs, Bundled Crossings Revisited, Fugitive-search games on graphs and related parameters, PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA, The pagenumber of \(k\)-trees is \(O(k)\), Properties of graphs specified by a regular language, A meta-theorem for distributed certification, On \(H\)-topological intersection graphs, Parameterized complexity of satisfactory partition problem, Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs, Unnamed Item, Offensive alliances in graphs, Circumference and Pathwidth of Highly Connected Graphs, Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
Cites Work
