scientific article

Publication date: 1979

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

matching planar graphs NP-completeness connectivity shortest paths minimum spanning tree planarity testing depth- first search optimum branching problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01)

Related Items (only showing first 100 items - show all)

Safe separators for treewidth ⋮ A logical query language for hypermedia systems ⋮ Minimum cuts in geometric intersection graphs ⋮ A linear algorithm for embedding planar graphs using PQ-trees ⋮ A unified approach to visibility representations of planar graphs ⋮ Finding small simple cycle separators for 2-connected planar graphs ⋮ A linear-time algorithm for four-partitioning four-connected planar graphs ⋮ Path-based depth-first search for strong and biconnected components ⋮ Edge-connectivity augmentation problems ⋮ Parallel ear decomposition search (EDS) and st-numbering in graphs ⋮ An improved self-stabilizing algorithm for biconnectivity and bridge-connectivity ⋮ On the bit complexity of distributed computations in a ring with a leader ⋮ Approximation algorithms for treewidth ⋮ A new look at fault-tolerant network routing ⋮ Network-based heuristics for constraint-satisfaction problems ⋮ The multi-tree approach to reliability in distributed networks ⋮ Computing Eulerian trails ⋮ Establishing order in planar subdivisions ⋮ A four-valued semantics for terminological logics ⋮ Supercube: An optimally fault tolerant network architecture ⋮ The k most vital arcs in the shortest path problem ⋮ Independence entropy of \(\mathbb{Z}^{d}\)-shift spaces ⋮ Rubber bands, convex embeddings and graph connectivity ⋮ Optimal fault-tolerant routings with small routing tables for \(k\)-connected graphs ⋮ Algorithms for plane representations of acyclic digraphs ⋮ Fast algorithms for robust classification with Bayesian nets ⋮ Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases ⋮ Topological morphing of planar graphs ⋮ A heuristic method to rectify intransitive judgments in pairwise comparison matrices ⋮ The maximum flow problem of uncertain network ⋮ Decomposing a relation into a tree of binary relations ⋮ Computing Euclidean maximum spanning trees ⋮ A new \(O(n^ 2)\) shortest chain algorithm ⋮ Partitioning multi-edge graphs ⋮ Dynamic maintenance of planar digraphs, with applications ⋮ Constructing full spanning trees for cubic graphs ⋮ Introduction to graph grammars with applications to semantic networks ⋮ Bipartite graphs, upward drawings, and planarity ⋮ The maximum flow problem is log space complete for P ⋮ Complexity of finding k-path-free dominating sets in graphs ⋮ The global theory of paths in networks. I: Definitions, examples and limits ⋮ A theory of rectangular dual graphs ⋮ A solution of the Sperner-Erdős problem ⋮ On the thickness of graphs of given degree ⋮ Optimal deadlock resolutions in edge-disjoint reducible wait-for graphs ⋮ Trémaux trees and planarity ⋮ Optimal covering of cacti by vertex-disjoint paths ⋮ Fusion and propagation with multiple observations in belief networks ⋮ Temporal constraint networks ⋮ Reducing conflict resolution time for solving graph problems in broadcast communications ⋮ Optimal fault-tolerant routings for connected graphs ⋮ An efficient distributed algorithm for centering a spanning tree of a biconnected graph ⋮ A model classifying algorithms as inherently sequential with applications to graph searching ⋮ Routing on trees ⋮ The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ A new graph triconnectivity algorithm and its parallelization ⋮ Coalition formation under limited communication ⋮ Recognition of DFS trees: Sequential and parallel algorithms with refined verifications ⋮ On paths with the shortest average arc length in weighted graphs ⋮ An algorithm for min-cost edge-disjoint cycles and its applications ⋮ A lower bound on the period length of a distributed scheduler ⋮ Upward drawings of triconnected digraphs. ⋮ A note on the construction of error detecting/correcting prefix codes ⋮ Treewidth computations. I: Upper bounds ⋮ A model for determining the cost-effectiveness of T1 transmission in certain integrated networks ⋮ Polyhedron complexes with simply transitive group actions and their realizations ⋮ A minimum 3-connectivity augmentation of a graph ⋮ I/O- and CPU-optimal recognition of strongly connected components ⋮ Polymatroidal flows with lower bounds ⋮ Fast random generation of binary, t-ary and other types of trees ⋮ Creating an acceptable consensus ranking for group decision making ⋮ Output feedback stabilization for a class of nonlinear time-evolution systems ⋮ On embedding a cycle in a plane graph ⋮ The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm ⋮ Proving mutual termination ⋮ Dynamic detection of subgraphs in computer networks ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ 2-partition-transitive tournaments ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ On approximation problems related to the independent set and vertex cover problems ⋮ Ramsey numbers and an approximation algorithm for the vertex cover problem ⋮ Graph traversals, genes and matroids: An efficient case of the travelling salesman problem ⋮ Interactive construction of graphical decision models based on causal mechanisms ⋮ Reliable communication over partially authenticated networks ⋮ A general program scheme for finding bridges ⋮ The complexity of determining a shortest cycle of even length ⋮ The path matrix of a graph, its construction and its use in evaluating certain products ⋮ Certain NP-complete matching problems ⋮ A simple version of Karzanov's blocking flow algorithm ⋮ On binary tree encodements ⋮ Finding pseudoperipheral nodes in graphs ⋮ Minimum-weight vertex cover problem for two-class resource connection graphs ⋮ Finding Euler tours in parallel ⋮ A new distributed depth-first-search algorithm ⋮ On area-efficient drawings of rectangular duals for VLSI floor-plan ⋮ Queue-mergesort ⋮ Qualitative decomposition of the eigenvalue problem in a dynamic system ⋮ Improved algorithms for graph four-connectivity ⋮ Self-stabilizing depth-first search

This page was built for publication: