scientific article; zbMATH DE number 3688740

Publication date 1979

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

Mathematics Subject Classification ID

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

Cited in

(only showing first 100 items - show all)

Output feedback stabilization for a class of nonlinear time-evolution systems
On embedding a cycle in a plane graph
Approximating the maximum clique minor and some subgraph homeomorphism problems
Interactive construction of graphical decision models based on causal mechanisms
The complexity of determining a shortest cycle of even length
A new distributed depth-first-search algorithm
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
Edge-connectivity augmentation problems
Parallel ear decomposition search (EDS) and st-numbering in graphs
On the bit complexity of distributed computations in a ring with a leader
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
Rubber bands, convex embeddings and graph connectivity
Algorithms for plane representations of acyclic digraphs
Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases
Constructing full spanning trees for cubic graphs
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 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
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
A model classifying algorithms as inherently sequential with applications to graph searching
A new graph triconnectivity algorithm and its parallelization
Coalition formation under limited communication
An algorithm for min-cost edge-disjoint cycles and its applications
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
The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm
Dynamic detection of subgraphs in computer networks
2-partition-transitive tournaments
Graph traversals, genes and matroids: An efficient case of the travelling salesman problem
Reliable communication over partially authenticated networks
Minimum-weight vertex cover problem for two-class resource connection graphs
Queue-mergesort
Self-stabilizing depth-first search
A logical query language for hypermedia systems
A graph approximation heuristic for the vertex cover problem on planar graphs
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
Exact solutions for the construction of optimal length test sequences
At most single-bend embeddings of cubic graphs
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
Grid embedding of 4-connected plane graphs
Partial breakdown in two-factor models
Reliability evaluation of large telecommunication networks
A greedy algorithm for the optimal basis problem
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
On the complexity of specification morphisms
Farrell polynomials on graphs of bounded tree width
Decomposition of a hypergraph by partial-edge separators
Three-dimensional orthogonal graph drawing algorithms
Simple and efficient network decomposition and synchronization
Fixed-parameter complexity in AI and nonmonotonic reasoning
Backjump-based backtracking for constraint satisfaction problems
A clustering algorithm based on graph connectivity
Joint convergence of random quadrangulations and their cores
On a class of branching problems in broadcasting and distribution
A simple linear-time algorithm for the recognition of bandwidth-2 biconnected graphs
``Global graph problems tend to be intractable
An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees
On the orderability problem for PLA folding
On the NP-hardness of edge-deletion and -contraction problems
Characterizations of consistent marked graphs
The complexity of planarity testing
Nearly sign-nonsingular matrices
Searching for acyclic orientations of graphs
The parallel complexity of growth models
Propositional semantics for disjunctive logic programs
Search for all \(d\)-mincuts of a limited-flow network
On private computation in incomplete networks
Optimal path cover problem on block graphs
Deciding bisimilarity and similarity for probabilistic processes.
Quantum algorithm for Feynman loop integrals
Separators and adjustment sets in causal graphs: complete criteria and an algorithmic framework
A simple 3-edge connected component algorithm revisited
A fast parallel algorithm for minimum-cost small integral flows
Inconsistency analysis by approximately specified priorities

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3883524)