Call routing and the ratcatcher
From MaRDI portal
Publication:1330799
DOI10.1007/BF01215352zbMath0799.05057OpenAlexW2019137761MaRDI QIDQ1330799
Publication date: 11 August 1994
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01215352
Hypergraphs (05C65) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
An algorithmic metatheorem for directed treewidth, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, (Total) vector domination for graphs with bounded branchwidth, On the minimum corridor connection problem and other generalized geometric problems, Approximate tree decompositions of planar graphs in linear time, An analysis of the parameterized complexity of periodic timetabling, Fixed-Parameter Tractability of Treewidth and Pathwidth, Approximation algorithms for treewidth, New analysis and computational study for the planar connected dominating set problem, The branchwidth of graphs and their cycle matroids, A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs, Subexponential Fixed-Parameter Algorithms for Partial Vector Domination, Unnamed Item, Rank-width: algorithmic and structural results, Constructive linear time algorithms for branchwidth, Finding branch-decompositions of matroids, hypergraphs, and more, Efficient reassembling of three-regular planar graphs, Improved induced matchings in sparse graphs, A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three, Approximation Algorithms for Euler Genus and Related Problems, Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract), A width parameter useful for chordal and co-comparability graphs, Improved bounds on the planar branchwidth with respect to the largest grid minor size, Practical algorithms for branch-decompositions of planar graphs, On self-duality of branchwidth in graphs of bounded genus, A note on planar graphs with large width parameters and small grid-minors, A combinatorial optimization algorithm for solving the branchwidth problem, An FPT 2-approximation for tree-cut decomposition, On the monotonicity of games generated by symmetric submodular functions., Proper interval vertex deletion, Catalan structures and dynamic programming in \(H\)-minor-free graphs, Parameterized complexity of graph planarity with restricted cyclic orders, Chordal embeddings of planar graphs, Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, Square roots of minor closed graph classes, Tangle and Maximal Ideal, Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds, Subexponential parameterized algorithms, Branch decomposition heuristics for linear matroids, Faster parameterized algorithms for minor containment, Characterizing graphs of small carving-width, Minimum restricted diameter spanning trees., Confronting intractability via parameters, Treewidth lower bounds with brambles, The Effect of Planarization on Width, Cutwidth: obstructions and algorithmic aspects, The structure of graphs not admitting a fixed immersion, Spanners in sparse graphs, Implicit branching and parameterized partial cover problems, An annotated bibliography on guaranteed graph searching, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, Computational study on a PTAS for planar dominating set problem, Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, Packing and covering immersions in 4-edge-connected graphs, Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs, Linearity of grid minors in treewidth with applications through bidimensionality, Subexponential fixed-parameter algorithms for partial vector domination, Connected graph searching, Fast minor testing in planar graphs, Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs, Branchwidth of chordal graphs, Computing branchwidth via efficient triangulations and blocks, Kernels in planar digraphs, Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs, Computing the branchwidth of interval graphs, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms, Unnamed Item, Treewidth computations. II. Lower bounds, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, The carving-width of generalized hypercubes, Unnamed Item, Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs, Computing rank-width exactly, Fixed-parameter tractability results for full-degree spanning tree and its dual, Treewidth, crushing and hyperbolic volume, Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs, Communication tree problems, The carvingwidth of hypercubes, The Effect of Planarization on Width, Minor-Minimal Planar Graphs of Even Branch-Width, The role of planarity in connectivity problems parameterized by treewidth, C-planarity testing of embedded clustered graphs with bounded dual carving-width, A Local Search Algorithm for Branchwidth, Unnamed Item, A SAT Approach to Branchwidth, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, Upward Book Embeddings of st-Graphs, Nondeterministic graph searching: from pathwidth to treewidth, On planar graphs with large tree-width and small grid minors, Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs, Improved Induced Matchings in Sparse Graphs, Computational study on planar dominating set problem, On spanning tree congestion of graphs, On the Tree-Width of Planar Graphs, Finding Branch-Decompositions of Matroids, Hypergraphs, and More, Connected Graph Searching in Outerplanar Graphs, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS, Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms, Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs, Combinatorics. Abstracts from the workshop held January 1--7, 2023, Upward book embeddability of \(st\)-graphs: complexity and algorithms, Treelength of series-parallel graphs, Tangle bases: Revisited, Simulation of quantum many-body systems on Amazon cloud, Branchwidth is \((1, g)\)-self-dual, Bounding branch-width, A Survey on the Complexity of Flood-Filling Games, Hardness of computing width parameters based on branch decompositions over the vertex set, Hardness of computing width parameters based on branch decompositions over the vertex set, Dynamic programming for graphs on surfaces, Tree decompositions and social graphs, Unnamed Item, Unnamed Item
Cites Work
