The arborescence-realization problem

DOI10.1016/0166-218X(93)E0170-4zbMath0834.68093OpenAlexW2081601236MaRDI QIDQ1893159

Donald K. Wagner, R. P. Swaminathan

Publication date: 3 July 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)e0170-4

zbMATH Keywords

arborescence graphicarborescence realizationHorn satisfiability problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Logic in artificial intelligence (68T27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

On computing the Galois lattice of bipartite distance hereditary graphs, On the Galois Lattice of Bipartite Distance Hereditary Graphs, Mixed logical-linear programming, On finding solutions for extended Horn formulas, On the complexity of recognizing directed path families, On exact selection of minimally unsatisfiable subformulae, Recognizing Helly edge-path-tree graphs and their clique graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Whitney's 2-switching theorem, cycle spaces, and arc mappings of directed graphs
• An efficient PQ-graph algorithm for solving the graph-realization problem
• Information storage and retrieval - mathematical foundations. II: Combinatorial problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• An Almost Linear-Time Algorithm for Graph Realization
• A Combinatorial Decomposition Theory
• Reliability covering problems
• Extended Horn sets in propositional logic
• 2-Isomorphic Graphs
• Dividing a Graph into Triconnected Components