Intersection representations of matrices by subtrees and unicycles on graphs

DOI10.1016/J.JDA.2007.08.001zbMATH Open1146.05033OpenAlexW2077900886MaRDI QIDQ935839FDOQ935839

Authors: Fanica Gavril, Shmuel Zaks, Ron Y. 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

Recommendations

• scientific article; zbMATH DE number 3912430
• scientific article; zbMATH DE number 4116559
• On the consecutive ones property
• Representations of bicircular matroids
• An Almost Linear-Time Algorithm for Graph Realization

zbMATH Keywords

hypergraphintersection graphunicycle graphbiological network clusteringintersection representation of a matrix

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

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

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

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