scientific article

Publication date: 1990

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

separation approximation algorithms vertex graph search path width gate matrix layout interval graph augmentation linear VLSI layout architectures matching problems with side constraints PLA folding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (51)

A linear time algorithm to list the minimal separators of chordal graphs ⋮ A generalized insertion algorithm for the seriation problem ⋮ PLA folding in special graph classes ⋮ Graph theoretic analysis of PLA folding heuristics ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ A column generation approach to job grouping for flexible manufacturing systems ⋮ Memory requirements for table computations in partial k-tree algorithms ⋮ The pathwidth and treewidth of cographs ⋮ A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ Triangulating graphs without asteroidal triples ⋮ Approximate search strategies for weighted trees ⋮ Fugitive-search games on graphs and related parameters ⋮ Helicopter search problems, bandwidth and pathwidth ⋮ Triangulating multitolerance graphs ⋮ The interval order polytope of a digraph ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Connected search for a lazy robber ⋮ The complexity of zero-visibility cops and robber ⋮ Connections between cutting-pattern sequencing, VLSI design, and flexible machines ⋮ Unnamed Item ⋮ Interval degree and bandwidth of a graph ⋮ On the monotonicity of games generated by symmetric submodular functions. ⋮ Generic algorithms for some decision problems on fasciagraphs and rotagraphs ⋮ An annotated bibliography on guaranteed graph searching ⋮ \(\alpha\)-vertex separator is NP-hard even for 3-regular graphs ⋮ The complexity of minimum-length path decompositions ⋮ Node-searching problem on block graphs ⋮ Narrowness, pathwidth, and their application in natural language processing ⋮ A simple linear-time algorithm for finding path-decompositions of small width ⋮ Mixed searching and proper-path-width ⋮ Intervalizing k-colored graphs ⋮ How to use the minimal separators of a graph for its chordal triangulation ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ Connected graph searching ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ Fugitive-search games on graphs and related parameters ⋮ CSP duality and trees of bounded pathwidth ⋮ Linear layouts measuring neighbourhoods in graphs ⋮ A biased random-key genetic algorithm for the minimization of open stacks problem ⋮ Derivation of algorithms for cutwidth and related graph layout parameters ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Combinatorial optimization models for production scheduling in automated manufacturing systems ⋮ Triangulating graphs with few \(P_4\)'s ⋮ Edge and node searching problems on trees ⋮ The minimization of open stacks problem: a review of some properties and their use in pre-processing operations ⋮ Algorithms and obstructions for linear-width and related search parameters ⋮ A heuristic and an exact method for the gate matrix connection cost minimization problem ⋮ On the pathwidth of chordal graphs ⋮ Searching expenditure and interval graphs ⋮ Minimal acyclic forbidden minors for the family of graphs with bounded path-width

This page was built for publication: