Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
From MaRDI portal
Publication:4327821
DOI10.1006/jagm.1995.1009zbMath0818.68118OpenAlexW2027562075WikidataQ59567984 ScholiaQ59567984MaRDI QIDQ4327821
John R. Gilbert, Ton Kloks, Hjálmtýr Hafsteinsson, Hans L. Bodlaender
Publication date: 20 August 1995
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/e7ca82a955ae64bd43159099b39ae4053dbff3e7
Related Items
A polynomial excluded-minor approximation of treedepth, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs, Tree-decompositions with bags of small diameter, Structural Parameterizations of the Mixed Chinese Postman Problem, Vertex rankings of chordal graphs and weighted trees, Fixed-Parameter Tractability of Treewidth and Pathwidth, On Universal Graphs of Minor Closed Families, Approximation algorithms for treewidth, Combining intensification and diversification strategies in VNS. An application to the vertex separation problem, Separators and structure prediction in sparse orthogonal factorization, Variable neighborhood search for the vertex separation problem, Characterizing width two for variants of treewidth, Space-efficient vertex separators for treewidth, Treewidth for graphs with small chordality, Characterizations and algorithmic applications of chordal graph embeddings, Flow metrics, Unnamed Item, Graph Bisection with Pareto Optimization, The \(k\)-strong induced arboricity of a graph, Constructing a minimum height elimination tree of a tree in linear time, On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability, Approximate search strategies for weighted trees, Edge ranking of graphs is hard, An algorithmic framework for locally constrained homomorphisms, Polynomial expansion and sublinear separators, Edge-treewidth: algorithmic and combinatorial properties, Complexity and Algorithms for Well-Structured k-SAT Instances, A \(p\)-centered coloring for the grid using \(O(p)\) colors, Computing densest \(k\)-subgraph with structural parameters, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, Fission: Practical algorithms for computing minimum balanced node separators, Shallow Minors, Graph Products, and Beyond-Planar Graphs, Induced subgraphs and path decompositions, A Modern View on Stability of Approximation, Unnamed Item, Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space, A strengthening and an efficient implementation of Alon-Tarsi list coloring method, Approximating the treewidth of AT-free graphs., Graph unique-maximum and conflict-free colorings, Unnamed Item, Finding the edge ranking number through vertex partitions, Ordered coloring of grids and related graphs, Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis, On the tree-depth of random graphs, On the vertex ranking problem for trapezoid, circular-arc and other graphs, Arankings of trees, On treewidth approximations., Compact navigation and distance oracles for graphs with small treewidth, Digraph measures: Kelly decompositions, games, and orderings, Solving Graph Problems via Potential Maximal Cliques, Approximation algorithms for digraph width parameters, Line graphs of bounded clique-width, Computing tree-depth faster than \(2^n\), The complexity of subgraph isomorphism for classes of partial k-trees, Minimizing elimination tree height can increase fill more than linearly, Complexity of rainbow vertex connectivity problems for restricted graph classes, On the diameter of tree associahedra, Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm, Connected graph searching, On tradeoffs between width- and fill-like graph parameters, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA, Treewidth computations. I: Upper bounds, Parameterized algorithms for the happy set problem, Tree decompositions with small cost, A sufficiently fast algorithm for finding close to optimal clique trees, Tree-depth, subgraph coloring and homomorphism bounds, Edge ranking of weighted trees, Unnamed Item, Unnamed Item, Linear layouts measuring neighbourhoods in graphs, Linear ordering based MIP formulations for the vertex separation or pathwidth problem, A $c^k n$ 5-Approximation Algorithm for Treewidth, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Scattered Classes of Graphs, Assortment optimization under the multinomial logit model with product synergies, Lower bounds for treewidth of product graphs, A partial k-arboretum of graphs with bounded treewidth, Structurally parameterized \(d\)-scattered set, Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited, Triangulating graphs with few \(P_4\)'s, Unnamed Item, The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth, Ordered Coloring Grids and Related Graphs, Conjunctive query containment revisited, Tree decompositions and social graphs, On vertex rankings of graphs and its relatives, Unnamed Item, On the tree-depth and tree-width in heterogeneous random graphs, Competitive Online Search Trees on Trees, Circumference and Pathwidth of Highly Connected Graphs, Listing all potential maximal cliques of a graph
