scientific article

Publication date: 1985

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

computational complexity graph algorithm NP-complete

Graph theory (including graph drawing) in computer science (68R10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Graph theory (05Cxx)

Related Items

Linear-size formulations for connected planar graph partitioning and political districting ⋮ Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality ⋮ Ruleset optimization on isomorphic oritatami systems ⋮ Robust partial synchronization of delay-coupled networks ⋮ Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2 ⋮ Commuting projections on graphs ⋮ The Kronecker product and local computations in graphs ⋮ ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH ⋮ Partitioning permutations into monotone subsequences ⋮ Interfacing architectural CAD data with KBS technology ⋮ On the zero divisor graphs of the ring of Lipschitz integers modulo \(n\) ⋮ Local base station assignment with time intervals in mobile computing environments ⋮ Linear-size planar Manhattan network for convex point sets ⋮ Evaluating efficiency of self-reconfiguration in a class of modular robots ⋮ The complexity of planarity testing ⋮ Criteria for a Structure to be Mesoionic ⋮ An algorithm for an Eulerian trail traversing specified edges in given order ⋮ A logic for reasoning about time and reliability ⋮ A Method for Computation and Analysis of Partial Synchronization Manifolds of Delay Coupled Systems ⋮ Detecting 2-joins faster ⋮ Dispersal routes reconstruction and the minimum cost arborescence problem ⋮ Developing a mathematical model for bobbin lace ⋮ The four-in-a-tree problem in triangle-free graphs ⋮ Perfect pairs of trees in graphs ⋮ On the use of ordered sets in problems of comparison and consensus of classifications ⋮ Structural Vulnerability and Robustness in Complex Networks: Different Approaches and Relationships Between them ⋮ Using a minimal number of resets when testing from a finite state machine ⋮ Question-guided stubborn set methods for state properties ⋮ On acyclic molecular graphs with prescribed numbers of edges that connect vertices with given degrees ⋮ Alternating Cell Direction Implicit Method Using Approximate Factorization on Hybrid Grids ⋮ Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs ⋮ Solving shortest paths efficiently on nearly acyclic directed graphs ⋮ Automatized Search for Complex Symbolic Dynamics with Applications in the Analysis of a Simple Memristor Circuit ⋮ BRS-compactness in networks: Theoretical considerations related to cohesion in citation graphs, collaboration networks and the internet ⋮ Planarity and Genus of Sparse Random Bipartite Graphs ⋮ Multigraph representations of hierarchical loglinear models ⋮ A two-step communication opinion dynamics model with self-persistence and influence index for social networks based on the DeGroot model ⋮ Balanced zero-divisor graphs of matrix rings. ⋮ The \(k\)-in-a-tree problem for graphs of girth at least \(k\) ⋮ Orienting cycle elements in orientable rotation systems ⋮ An annotated bibliography on 1-planarity ⋮ On the assessment of learning in competence based knowledge space theory ⋮ Efficient enumeration of all minimal separators in a graph ⋮ On the performance and feasibility of multicast core selection heuristics ⋮ Improved shortest path algorithms for nearly acyclic graphs ⋮ Algebraic multigrid methods ⋮ Application of a neural network to a design optimization process ⋮ Fast rendezvous with advice ⋮ A NOTE ON FRACTALS OF ONE FORBIDDEN WORD AND THEIR BOX DIMENSIONS ⋮ Different local controls for graph relabeling systems ⋮ An efficient implementation of the equilibrium algorithm for housing markets with duplicate houses ⋮ Errors in graph embedding algorithms ⋮ A large set of torus obstructions and how they were discovered ⋮ Network topology of the interbank market ⋮ Optimal path cover problem on block graphs ⋮ Fuzzy decision networks and deconvolution ⋮ Edge local complementation for logical cluster states ⋮ The complexity of the empire colouring problem ⋮ Problems on pairs of trees and the four colour problem of planar graphs ⋮ Modelling and analysis of distributed program execution in BETA using coloured Petri Nets ⋮ Matchings and cycle covers in random digraphs ⋮ On the largest strong components in \(m\)-out digraphs ⋮ Estimating transmission from genetic and epidemiological data: a metric to compare transmission trees ⋮ Efficient algorithms for subgraph listing ⋮ Algorithms for generating labelled graphs with given degree ⋮ Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem ⋮ Dependency graphs and mass conservation in reaction systems ⋮ The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate ⋮ Guthrie's problem: new equivalences and rapid reductions ⋮ On depth first search trees in \(m\)-out digraphs ⋮ Distributed disassembly of mosaics ⋮ Modelling deadlock in open restricted queueing networks ⋮ A parallel routing algorithm on recursive cube of rings networks employing Hamiltonian circuit Latin square ⋮ Supertropical matrix algebra ⋮ Treewidth computations. I: Upper bounds ⋮ Tropical compound matrix identities ⋮ An algebraic multilevel method for anisotropic elliptic equations based on subgraph matching ⋮ Cartesian graph factorization at logarithmic cost per edge ⋮ Decomposing toroidal graphs into circuits and edges ⋮ \texttt{Code \(C\sharp\)} for chaos analysis of relativistic many-body systems ⋮ AN AVERAGING PRINCIPLE FOR COMBINED INTERACTION GRAPHS — CONNECTIVITY AND APPLICATIONS TO GENETIC SWITCHES ⋮ Feature-based operation sequence generation in CAPP ⋮ Rotation sequences and edge-colouring of binary tree pairs ⋮ A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs ⋮ Designing optimally multiplexed SNP genotyping assays ⋮ An algorithm for computing simple \(k\)-factors ⋮ On finding fundamental cut sets ⋮ Relaxation to equilibrium of generalized east processes on \(\mathbb{Z}^{d}\): renormalization group analysis and energy-entropy competition ⋮ Computational geometric aspects of rhythm, melody, and voice-leading ⋮ Euler's Königsberg: the explanatory power of mathematics ⋮ An Event-Driven Algorithm for Agents on the Web ⋮ Stabilizing maximum matching in bipartite networks ⋮ A mean-field monomer-dimer model with randomness: exact solution and rigorous results ⋮ Three-quarter approximation for the number of unused colors in graph coloring ⋮ Nonlinear game models for large-scale network bandwidth management ⋮ Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem ⋮ Graph-theoretical analysis of the Swiss road and railway networks over time ⋮ A Category-Theoretic Approach to Social Network Analysis ⋮ Modulation in tetradic harmony and its role in jazz ⋮ On a simple randomized algorithm for finding a 2-factor in sparse graphs ⋮ A model search procedure for hierarchical models ⋮ A structural analysis of topic ontologies ⋮ A multi-time-scale analysis of chemical reaction networks. I: Deterministic systems ⋮ Application of the special Latin square to a parallel routing algorithm on a recursive circulant network. ⋮ Retrieval by classification of images containing large manmade objects using perceptual grouping ⋮ Unified approach to fuzzy graph problems ⋮ A Linear-Time Algorithm for Finding Induced Planar Subgraphs