Incidence matrices and interval graphs
Open accessThe DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Abstract
According to present genetic theory, the fine structure of genes consists of linearly ordered elements.A mutant gene is obtained by alteration of some connected portion of this structure.By examining data obtained from suitable experiments, it can be determined whether or not the blemished portions of two mutant genes intersect or not, and thus intersection data for a large number of mutants can be represented as an undirected graph.If this graph is an "interval graph," then the observed data is consistent with a linear model of the gene.The problem of determining when a graph is an interval graph is a special case of the following problem concerning (0, l)-matrices: When can the rows of such a matrix be permuted so as to make the l's in each column appear consecutively?A complete theory is obtained for this latter problem, culminating in a decomposition theorem which leads to a rapid algorithm for deciding the question, and for constructing the desired permutation when one exists.Let A -(dij) be an m by n matrix whose entries a i3 are all either 0 or 1.The matrix A may be regarded as the incidence matrix of elements e l9 e 2 , , e m vs. sets S l9 S 2 , , S n ; that is, a i3 = 0 or 1 according as e t is not or is a member of S 3 .For certain applications, one of which will be discussed below, it is of interest to know whether or not one can order the elements in such a way that each set S 3 consists of elements that appear consecutively in the ordering.In terms of the incidence matrix A, the question is whether there is an m by m permutation matrix P such that the Γs in each column of PA occur in consecutive positions.We shall describe a computationally efficient method of answering this question, and of determining such a P when one exists.Given a family of sets S lf S 29 , S n , one can form the intersection graph of the family by associating a vertex of the graph with each set and joining two distinct vertices with an edge if their corresponding sets have a nonempty intersection.Conversely, any finite graph can of course be viewed as the intersection graph of a family of sets (in many ways).If each set can be taken as an interval on the real line, the graph is called an interval graph.Interval graphs have been investigated in [7,5,3].The problem posed above is closely related to that of determining whether a given graph is an interval
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Dirac, G. A. (1961) · Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg · doi:10.1007/bf02992776 · Cited by 927
Representation of a finite graph by a set of intervals on the real line
Lekkeikerker, C., & Boland, J. (1962) · Fundamenta Mathematicae · doi:10.4064/fm-51-1-45-64 · Cited by 710
ON THE TOPOLOGY OF THE GENETIC FINE STRUCTURE
Benzer, S. (1959) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.45.11.1607 · Cited by 398
Integral Boundary Points of Convex Polyhedra
Hoffman, A. J., & Kruskal, J. B. (2010) · 50 Years of Integer Programming 1958-2008 · doi:10.1007/978-3-540-68279-0_3 · Cited by 369
Cited by
Booth, K. S., & Lueker, G. S. (1976) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(76)80045-1 · Cited by 1,488
Algorithmic Aspects of Vertex Elimination on Graphs
Rose, D. J., Tarjan, R. E., & Lueker, G. S. (1976) · SIAM Journal on Computing · doi:10.1137/0205021 · Cited by 1,203
Tarjan, R. E., & Yannakakis, M. (1984) · SIAM Journal on Computing · doi:10.1137/0213035 · Cited by 1,058
Triangulated graphs and the elimination process
Rose, D. J. (1970) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(70)90282-9 · Cited by 500
Waki, H., Kim, S., Kojima, M., & Muramatsu, M. (2006) · SIAM Journal on Optimization · doi:10.1137/050623802 · Cited by 439
An Introduction to Chordal Graphs and Clique Trees
Blair, J. R. S., & Peyton, B. (1993) · The IMA Volumes in Mathematics and its Applications · doi:10.1007/978-1-4613-8369-7_1 · Cited by 377
Unit disk graph recognition is NP-hard
Breu, H., & Kirkpatrick, D. G. (1998) · Computational Geometry · doi:10.1016/s0925-7721(97)00014-x · Cited by 312
Estimating high-dimensional intervention effects from observational data
Maathuis, M. H., Kalisch, M., & Bühlmann, P. (2009) · The Annals of Statistics · doi:10.1214/09-aos685 · Cited by 312
Finding a Maximum Clique in an Arbitrary Graph
Balas, E., & Yu, C. S. (1986) · SIAM Journal on Computing · doi:10.1137/0215075 · Cited by 295
A survey of sparse matrix research
Duff, I. S. (1977) · Proceedings of the IEEE · doi:10.1109/proc.1977.10514 · Cited by 262
Toward Quantum Gate-Model Heuristics for Real-World Planning Problems
Stollenwerk, T., Hadfield, S., & Wang, Z. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3030609 · Cited by 29
Metadata
- Authors
- Fulkerson, D., & Gross, O.
- Venue
- Pacific Journal of Mathematics
- Publisher
- Mathematical Sciences Publishers
- Published
- 1965-09-01
- Volume
- 15
- Issue
- 3
- Pages
- 835-855
- ISSN
- 0030-8730 (ISSN-L)
- OpenAlex
- W2089465933
- Cited by
- 1,262
- References
- 4
- FWCI
- 13.36
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.