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

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, Trémaux Trees and Planarity, All Circuits Enumeration in Macro-Econometric Models, A new notion of convexity in digraphs with an application to Bayesian networks, Toward a general theory of unicast-based multicast communication, Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs, Efficient algorithms for a mixed k-partition problem of graphs without specifying bases, DFS tree construction: Algorithms and characterizations, O(n2) algorithms for graph planarization, Bandwidth and profile minimization, A fuzzy max-flow min-cut theorem., Optimal collective dichotomous choice under partial order constraints, Communication in the two-way listen-in vertex-disjoint paths mode, The DFS-heuristic for orthogonal graph drawing, On Physical Mapping and the consecutive ones property for sparse matrices, Shuffling biological sequences, Constructing minimum changeover cost arborescenses in bounded treewidth graphs, Greedy approximation algorithms for directed multicuts, Multicastad hocrouting through mobility-aware Steiner tree meshes with consistency across different mobility models, Optimal Broadcast with Partial Knowledge, Characterizations of consistent marked graphs, A graph approximation heuristic for the vertex cover problem on planar graphs, Bicriteria product design optimization: An efficient solution procedure using AND/OR trees, Heuristics for scheduling resource-constrained projects in MPM networks, A linear algorithm for centering a spanning tree of a biconnected graph, Experimental evaluation of preprocessing algorithms for constraint satisfaction problems, Inconsistency analysis by approximately specified priorities, Exact solutions for the construction of optimal length test sequences, At most single-bend embeddings of cubic graphs, Graph theoretic analysis of PLA folding heuristics, Efficient reductions of picture words, Two-page book embedding of trees under vertex-neighborhood constraints, The complexity of planarity testing, Codes modulo finite monadic string-rewriting systems, Finding maximum matching for bipartite graphs in parallel, Planarity testing in parallel, Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity, Proof labeling schemes, Nearly sign-nonsingular matrices, How to draw a series-parallel digraph, A parallel approach to the Eulerian cycle problem, Deadline guaranteed packet scheduling for overloaded traffic in input-queued switches, Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract), On the capabilities of systolic systems, Searching for acyclic orientations of graphs, Grid embedding of 4-connected plane graphs, Partial breakdown in two-factor models, On finding an ear decomposition of an undirected graph distributively, The parallel complexity of growth models, Reliability evaluation of large telecommunication networks, A greedy algorithm for the optimal basis problem, Computing orthogonal drawings with the minimum number of bends, A complete characterization of the path layout construction problem for ATM networks with given hop count and load, On solving intransitivities in repeated pairwise choices, A BDD SAT solver for satisfiability testing: An industrial case study, A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, Algorithms for area-efficient orthogonal drawing, Propositional semantics for disjunctive logic programs, Sequential commitment games, Shortest edge-disjoint paths in graphs, On the complexity of specification morphisms, Uncovering trees in constraint networks, Farrell polynomials on graphs of bounded tree width, A polynomial algorithm determining cyclic vertex connectivity of \(k\)-regular graphs with fixed \(k\), A polynomial algorithm determining cyclic vertex connectivity of 4-regular graphs, Search for all \(d\)-mincuts of a limited-flow network, Search Games: A Review, A new correctness criterion for the proof nets of non-commutative multiplicative linear logics, On equilibria for ADM minimization games, Joint convergence of random quadrangulations and their cores, Reducing complexities of the distributed max-flow and breadth-first-search algorithms by means of network synchronization, On private computation in incomplete networks, The complexity of minimum cut and maximum flow problems in an acyclic network, Optimal path cover problem on block graphs, Introduction to Testing Graph Properties, Dynamical Systems Theory and Algorithms for NP-hard Problems, Noncontiguous pattern containment in binary trees, On the use of registers in achieving wait-free consensus, On the complexity of constructing minimum changeover cost arborescences, Partition-based logical reasoning for first-order and propositional theories, Deciding bisimilarity and similarity for probabilistic processes., Unnamed Item, Some properties of 2-threshold graphs, On a class of branching problems in broadcasting and distribution, Computing the probability distribution of project duration in a PERT network, Unnamed Item, Combinatorial Aspects of the Orrery Model of Syntax, A note on rectilinear and polar visibility graphs, Decomposing toroidal graphs into circuits and edges, Restricted unimodular chordal graphs, On the probabilistic minimum coloring and minimum \(k\)-coloring, Cost minimization in wireless networks with a bounded and unbounded number of interfaces, Identifying independence in bayesian networks, Approximation algorithms for graph augmentation, Cost Minimisation in Multi-interface Networks, A simple linear-time algorithm for the recognition of bandwidth-2 biconnected graphs, Unbounded-Thread Program Verification using Thread-State Equations, Introduction to Testing Graph Properties, A bidirectional heuristic for maximizing the net present value of large-scale projects subject to limited resources, ``Global graph problems tend to be intractable, An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees, Decomposition of a hypergraph by partial-edge separators, On the orderability problem for PLA folding, Three-dimensional orthogonal graph drawing algorithms, Message complexity versus space complexity in fault tolerant broadcast protocols, Separators and adjustment sets in causal graphs: complete criteria and an algorithmic framework, Low-connectivity network design on series-parallel graphs, An ex-post bound on the greedy heuristic for the uncapacitated facility location problem, Simple and efficient network decomposition and synchronization, Orthogonal representations over finite fields and the chromatic number of graphs, On the NP-hardness of edge-deletion and -contraction problems, Theory of computation of multidimensional entropy with an application to the monomer-dimer problem, Two-dimensional Sgraffito automata, Quantum algorithm for Feynman loop integrals, The Why, How, and When of Representations for Complex Systems, Fixed-parameter complexity in AI and nonmonotonic reasoning, A simple 3-edge connected component algorithm revisited, Backjump-based backtracking for constraint satisfaction problems, A clustering algorithm based on graph connectivity, A fast parallel algorithm for minimum-cost small integral flows