Graph minors. I. Excluding a forest
From MaRDI portal
Publication:1055450
DOI10.1016/0095-8956(83)90079-5zbMath0521.05062OpenAlexW2033405938WikidataQ29013762 ScholiaQ29013762MaRDI QIDQ1055450
Publication date: 1983
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(83)90079-5
Related Items
Bounding the search number of graph products, Algorithms, Complexity, and Hans, Memory management for Union-Find algorithms, Uniform Kernelization Complexity of Hitting Forbidden Minors, Positive Semidefinite Zero Forcing: Complexity and Lower Bounds, Labelled well-quasi-order for permutation classes, Memory requirements for table computations in partial k-tree algorithms, The pathwidth and treewidth of cographs, Probabilistic logic with independence, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, On the k-rainbow domination in graphs with bounded tree-width, A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, Decontamination of hypercubes by mobile agents, Pathwidth is NP-Hard for Weighted Trees, On the pathwidth of hyperbolic 3-manifolds, A Simpler Self-reduction Algorithm for Matroid Path-Width, Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs, Seymour's conjecture on 2-connected graphs of large pathwidth, Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs, Locating a robber with multiple probes, Interview with Don Knuth, Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets, Graph Minors I: A Short Proof of the Path-width Theorem, On the thinness and proper thinness of a graph, Characterizations and directed path-width of sequence digraphs, Separating layered treewidth and row treewidth, Stochastic approximation of lamplighter metrics, Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs, Edge-treewidth: algorithmic and combinatorial properties, Complexity and Algorithms for Well-Structured k-SAT Instances, On the complexity of the storyplan problem, The complexity of learning minor closed graph classes, Parameterized complexity of envy-free resource allocation in social networks, Optimal parallel shortest paths in small treewidth digraphs, The Rique-number of graphs, On Evasion Games on Graphs, On Strong Tree-Breadth, Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem, Mineurs d'arbres avec racines, On structural parameterizations of star coloring, Pathwidth of Circular-Arc Graphs, The Treewidth and Pathwidth of Graph Unions, Grad and classes with bounded expansion. I: Decompositions, Grad and classes with bounded expansion. II: Algorithmic aspects, Monoidal Width: Capturing Rank Width, Induced subgraphs and path decompositions, Unnamed Item, A distributed algorithm for computing the node search number in trees, Temporal matching on geometric graph data, Unnamed Item, Pathwidth, trees, and random embeddings, The theory of guaranteed search on graphs, Parameters Tied to Treewidth, Obstructions for linear rank-width at most 1, The complexity of register allocation, Minor-Closed Graph Classes with Bounded Layered Pathwidth, Counting solutions to CSP using generating polynomials, The “Art of Trellis Decoding” Is NP-Hard, Parameterized Algorithms for Book Embedding Problems, Orthogonal Tree Decompositions of Graphs, Line graphs of bounded clique-width, Node-searching problem on block graphs, A 3-approximation for the pathwidth of Halin graphs, A 3-approximation for the pathwidth of Halin graphs, What’s Decidable About Program Verification Modulo Axioms?, Solution to König's Graph Embedding Problem, A Practical Approach to Courcelle's Theorem, On the colored Tutte polynomial of a graph of bounded treewidth, Counting independent sets in graphs with bounded bipartite pathwidth, Excluding Subdivisions of Infinite Cliques, Clique-perfectness of complements of line graphs, Characterization of graphs and digraphs with small process numbers, Linear layouts measuring neighbourhoods in graphs, max-cut and Containment Relations in Graphs, A Quartic Kernel for Pathwidth-One Vertex Deletion, An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion, Tree-decompositions of small pathwidth, Graph classes and the switch Markov chain for matchings, Incremental optimization of independent sets under the reconfiguration framework, Excluding Infinite Trees, Unnamed Item, Branch decompositions and minor containment, Clique-perfectness of complements of line graphs, Using decomposition-parameters for QBF: mind the prefix!, FPT is characterized by useful obstruction sets, A Polynomial Time Algorithm for Bounded Directed Pathwidth, Erdös--Pósa Property for Labeled Minors: 2-Connected Minors, Comparing linear width parameters for directed graphs, Finding small-width connected path decompositions in polynomial time, On the hardness of palletizing bins using FIFO queues, On the relationship between NLC-width and linear NLC-width, Tournament minors, Zero-visibility cops and robber and the pathwidth of a graph, On L-shaped point set embeddings of trees: first non-embeddable examples, Well-quasi-order for permutation graphs omitting a path and a clique, Tree Pivot-Minors and Linear Rank-Width, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, On Treewidth and Related Parameters of Random Geometric Graphs, The treewidth and pathwidth of hypercubes, Treewidth of the generalized Kneser graphs, The edge-Erdős-Pósa property, Graph minors. V. Excluding a planar graph, Obstruction set isolation for the gate matrix layout problem, On the minimum eccentricity isometric cycle problem, A note on multiflows and treewidth, On exploring always-connected temporal graphs of small pathwidth, Contraction obstructions for connected graph searching, Computing directed pathwidth in \(O(1.89^n)\) time, An asymptotic analysis of labeled and unlabeled \(k\)-trees, Parameterized power domination complexity, Grids and their minors, New analysis and computational study for the planar connected dominating set problem, On embedding graphs in trees, On well-quasi-ordering-finite graphs by immersion, Characterizing width two for variants of treewidth, Strong-mixed searching and pathwidth, A local characterization of bounded clique-width for line graphs, Treewidth for graphs with small chordality, The mixed page number of graphs, Graphs with small bandwidth and cutwidth, Algorithmic uses of the Feferman-Vaught theorem, Probabilistic reasoning with graphical security models, Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions, Some recent progress and applications in graph minor theory, Transformations of cubic graphs, Treewidth and gonality of glued grid graphs, On minimum cost edge searching, Entanglement and the complexity of directed graphs, Random graphs from a weighted minor-closed class, Helicopter search problems, bandwidth and pathwidth, Triangulating multitolerance graphs, Optimization problems in dotted interval graphs, Grid minors in damaged grids, Crossing-number critical graphs have bounded path-width, The complexity of minimum convex coloring, Local search is a PTAS for feedback vertex set in minor-free graphs, Interval degree and bandwidth of a graph, Minesweeper on graphs, Filtration simplification for persistent homology via edge contraction, Tradeoffs in process strategy games with application in the WDM reconfiguration problem, Parameterized algorithms for book embedding problems, \textsc{max-cut} and containment relations in graphs, Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications, Clique-width of countable graphs: A compactness property., Towards tight(er) bounds for the excluded grid theorem, Practical algorithms for MSO model-checking on tree-decomposable graphs, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, Characterisations and examples of graph classes with bounded expansion, Quickly excluding a forest, Cellular resolutions of cointerval ideals, The complexity of minimum-length path decompositions, Track layouts, layered path decompositions, and leveled planarity, Narrowness, pathwidth, and their application in natural language processing, A simple linear-time algorithm for finding path-decompositions of small width, A review of two network curvature measures, Mixed searching and proper-path-width, Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs, Neighbourhood-width of trees, Forbidden directed minors and Kelly-width, Excluding infinite minors, Lower bounds for positive semidefinite zero forcing and their applications, On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon, Line-distortion, bandwidth and path-length of a graph, A counterexample regarding labelled well-quasi-ordering, Algorithmic meta-theorems for restrictions of treewidth, An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion, Bandwidth and pathwidth of three-dimensional grids, On the geometric Ramsey number of outerplanar graphs, Recent developments on graphs of bounded clique-width, Two feedback problems for graphs with bounded tree-width, Graph minor hierarchies, Computing the branchwidth of interval graphs, 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, Contiguous search problem in Sierpiński graphs, Glauber dynamics on trees and hyperbolic graphs, Excluding a large theta graph, Exclusive graph searching vs. pathwidth, Tree-width, path-width, and cutwidth, A spectral lower bound for the treewidth of a graph and its consequences, Derivation of algorithms for cutwidth and related graph layout parameters, Universal augmentation schemes for network navigability, Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion), The complexity of the vertex-minor problem, All structured programs have small tree width and good register allocation, Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms, A partial k-arboretum of graphs with bounded treewidth, The NLC-width and clique-width for powers of graphs of bounded tree-width, AND/OR search spaces for graphical models, Edge and node searching problems on trees, Computational study on planar dominating set problem, On computing graph minor obstruction sets, Submodular partition functions, Graph minors. III. Planar tree-width, On the pathwidth of chordal graphs, Counting \(H-\)colorings of partial \(k-\)trees, The structure of the models of decidable monadic theories of graphs, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, On the complexity of the storyplan problem, 2-Layer Graph Drawings with Bounded Pathwidth, Treewidth of the \(q\)-Kneser graphs, Tree-width and path-width of comparability graphs of interval orders, Locating Eigenvalues of Symmetric Matrices - A Survey
Cites Work
