Call routing and the ratcatcher
From MaRDI portal
Publication:1330799
DOI10.1007/BF01215352zbMATH Open0799.05057OpenAlexW2019137761WikidataQ131627655 ScholiaQ131627655MaRDI QIDQ1330799FDOQ1330799
Authors: Robin Thomas, Paul Seymour 
Publication date: 11 August 1994
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01215352
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Hypergraphs (05C65) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
Cited In (only showing first 100 items - show all)
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Improved induced matchings in sparse graphs
- An algorithmic metatheorem for directed treewidth
- A Survey on the Complexity of Flood-Filling Games
- On self-duality of branchwidth in graphs of bounded genus
- Linearity of grid minors in treewidth with applications through bidimensionality
- Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
- Treewidth computations. II. Lower bounds
- Constructive linear time algorithms for branchwidth
- On spanning tree congestion of graphs
- The branchwidth of graphs and their cycle matroids
- Spanners in sparse graphs
- The carving-width of generalized hypercubes
- A local search algorithm for branchwidth
- An annotated bibliography on guaranteed graph searching
- Proper interval vertex deletion
- A note on planar graphs with large width parameters and small grid-minors
- A combinatorial optimization algorithm for solving the branchwidth problem
- Branchwidth of chordal graphs
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Approximation algorithms for treewidth
- (Total) vector domination for graphs with bounded branchwidth
- Treewidth lower bounds with brambles
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- Square roots of minor closed graph classes
- Communication tree problems
- Chordal embeddings of planar graphs
- Fixed-parameter tractability results for full-degree spanning tree and its dual
- Computing branchwidth via efficient triangulations and blocks
- Implicit branching and parameterized partial cover problems
- Approximate tree decompositions of planar graphs in linear time
- Approximate tree decompositions of planar graphs in linear time
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Connected graph searching
- Approximation algorithms for Euler genus and related problems
- Improved induced matchings in sparse graphs
- Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
- Computing the branchwidth of interval graphs
- Characterizing graphs of small carving-width
- New analysis and computational study for the planar connected dominating set problem
- Minor-minimal planar graphs of even branch-width
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Subexponential parameterized algorithms
- The structure of graphs not admitting a fixed immersion
- Confronting intractability via parameters
- On the monotonicity of games generated by symmetric submodular functions.
- Practical algorithms for branch-decompositions of planar graphs
- On the minimum corridor connection problem and other generalized geometric problems
- The carvingwidth of hypercubes
- Rank-width: algorithmic and structural results
- Connected Graph Searching in Outerplanar Graphs
- Kernels in planar digraphs
- Faster parameterized algorithms for minor containment
- Subexponential parameterized algorithms for bounded-degree connected subgraph problems on planar graphs
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- Computational study on planar dominating set problem
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Computing rank-width exactly
- On planar graphs with large tree-width and small grid minors
- On the tree-width of planar graphs
- Nondeterministic graph searching: from pathwidth to treewidth
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Tree decompositions and social graphs
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Fixed-parameter tractability of treewidth and pathwidth
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Dynamic programming for graphs on surfaces
- Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
- Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- Cutwidth: obstructions and algorithmic aspects
- Tangle and Maximal Ideal
- Treewidth, crushing and hyperbolic volume
- A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
- Computational study on a PTAS for planar dominating set problem
- A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Fast FPT-approximation of branchwidth
- Branch decomposition heuristics for linear matroids
- Minimum restricted diameter spanning trees.
- Subexponential fixed-parameter algorithms for partial vector domination
- Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
- A SAT approach to branchwidth
- The effect of planarization on width
- Exact distance oracles for planar graphs
- Fast minor testing in planar graphs
- Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
- Title not available (Why is that?)
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Tangle bases: Revisited
- Upward book embeddings of st-graphs
- An analysis of the parameterized complexity of periodic timetabling
- Upward book embeddability of \(st\)-graphs: complexity and algorithms
- The role of twins in computing planar supports of hypergraphs
- Title not available (Why is that?)
- Bounding branch-width
- Subexponential fixed-parameter algorithms for partial vector domination
- C-planarity testing of embedded clustered graphs with bounded dual carving-width
This page was built for publication: Call routing and the ratcatcher
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1330799)
