Intersection representations of matrices by subtrees and unicycles on graphs

DOI10.1016/J.JDA.2007.08.001zbMath1146.05033OpenAlexW2077900886MaRDI QIDQ935839

Shmuel Zaks, Fanica Gavril, Ron Yair Pinter

Publication date: 8 August 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.08.001

zbMATH Keywords

hypergraphintersection graphunicycle graphbiological network clusteringintersection representation of a matrix

Mathematics Subject Classification ID

Trees (05C05) Applications of graph theory (05C90) Hypergraphs (05C65) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Circular-arc hypergraphs: rigidity via connectedness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Circular representation problem on hypergraphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A recognition algorithm for the intersection graphs of paths in trees
• Intersection graphs of concatenable subtrees of graphs
• A characterisation of rigid circuit graphs
• Intersection graphs of Helly families of subtrees
• A faster algorithm to recognize undirected path graphs
• Incidence matrices and interval graphs
• Maximal sub-triangulation in pre-processing phylogenetic data
• Matrix characterizations of circular-arc graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Generating the maximum spanning trees of a weighted graph
• Planar linear arrangements of outerplanar graphs
• Power of Natural Semijoins
• Algorithms on circular-arc graphs
• Acyclic Hypergraph Projections
• Recognition of Circle Graphs
• The Traveling-Salesman Problem and Minimum Spanning Trees
• A Simpler Linear-Time Recognition of Circular-Arc Graphs

This page was built for publication: Intersection representations of matrices by subtrees and unicycles on graphs