The arborescence-realization problem

DOI10.1016/0166-218X(93)E0170-4MaRDI QIDQ1893159zbMATH OpenOpenAlexFDO

Authors R. P. Swaminathan, Donald K. Wagner

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

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

Recommendations

• An Almost Linear-Time Algorithm for Graph Realization
• scientific article; zbMATH DE number 7692724
• Two Algorithms for Unranking Arborescences
• Exact arborescences, matchings and cycles
• The complexity of finding arborescences in hypergraphs

Cites work

• 2-Isomorphic Graphs
• A Combinatorial Decomposition Theory
• An Almost Linear-Time Algorithm for Graph Realization
• An efficient PQ-graph algorithm for solving the graph-realization problem
• Dividing a Graph into Triconnected Components
• Extended Horn sets in propositional logic
• Graph theory with applications
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• Information storage and retrieval - mathematical foundations. II: Combinatorial problems
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Reliability covering problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Whitney's 2-switching theorem, cycle spaces, and arc mappings of directed graphs

Cited in

(12)

• On exact selection of minimally unsatisfiable subformulae
• Mixed logical-linear programming
• Around the Danzer problem and the construction of dense forests
• Recognizing Helly edge-path-tree graphs and their clique graphs
• On computing the Galois lattice of bipartite distance hereditary graphs
• Arboral satisfaction: recognition and LP approximation
• On the Galois Lattice of Bipartite Distance Hereditary Graphs
• An Almost Linear-Time Algorithm for Graph Realization
• The Gilbert arborescence problem
• On finding solutions for extended Horn formulas
• Unit refutability of Horn constraint systems -- certification and parallel complexity
• On the complexity of recognizing directed path families

This page was built for publication: The arborescence-realization problem

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