Incidence matrices and interval graphs

DOI10.2140/pjm.1965.15.835zbMath0132.21001WikidataQ55952668 ScholiaQ55952668MaRDI QIDQ2395457

Publication date: 1965

Published in: Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2140/pjm.1965.15.835

zbMATH Keywords

topology

Related Items

Matrices with chordal inverse zero-patterns, Determinantal formulae and nonsymmetric gaussian perfect elimination, Complexity of approximating the oriented diameter of chordal graphs, Extremal interval graphs, SCHEDULING INTERVAL ORDERS IN PARALLEL, Consecutive cuts and paths, and bounds on k‐terminal reliability, Asymptotic enumeration of full graphs, On the computational complexity of ordered subgraph recognition, Enumeration of Full Graphs: Onset of the Asymptotic Region, Efficient parallel algorithms for bipartite permutation graphs, On the complexity of alpha conversion, Poincaré-Hopf inequalities, Characterizing circular-arc graphs, Partial orders of dimension 2, Algorithms for a maximum clique and a maximum independent set of a circle graph, Analysis of upper bounds for the pallet loading problem, Totally positive matrices and totally positive hypergraphs, On Physical Mapping and the consecutive ones property for sparse matrices, Minimizing phylogenetic number to find good evolutionary trees, Higher homotopy groups of complements of complex hyperplane arrangements, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, A characterization of graphs with interval two-step graphs, Recognition of some perfectly orderable graph classes, An extension of a theorem of Fulkerson and Gross, On the semi-perfect elimination, A good submatrix is hard to find, A survey of statistical problems in archaeological dating, A characterisation of rigid circuit graphs, A note on the consecutive ones submatrix problem., Generating and characterizing the perfect elimination orderings of a chordal graph, Polynomial approximation schemes and exact algorithms for optimum curve segmentation problems, Chordal probe graphs, Permuting matrices to avoid forbidden submatrices, Negative results on characterizing visibility graphs, On graphs without \(P_ 5\) and \(\overline {P}_ 5\), Characterizations of fuzzy interval graphs, On preemptive scheduling: A general setting for the two-phase method, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, Graph isomorphism and identification matrices: Sequential algorithms, Characterization of the graphs with boxicity \(\leq 2\), Optimal decomposition by clique separators, The story of perfectly orderable graphs, Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, Note on maximal split-stable subgraphs, On the Golod property of Stanley-Reisner rings, Extracting constrained 2-interval subsets in 2-interval sets, Tree decomposition and discrete optimization problems: a survey, A matrix characterization of interval and proper interval graphs, Representation characterizations of chordal bipartite graphs, Intransitive indifference with unequal indifference intervals, On nontransitive indifference, A structure theorem for the consecutive 1's property, Triangulated graphs and the elimination process, Betweenness, orders and interval graphs, Description of some relations on the set of real-line intervals, On the theory of the consecutive storage of relevant records, The intersection graphs of subtrees in trees are exactly the chordal graphs, Oracles for vertex elimination orderings, On double and multiple interval graphs, Efficient algorithms for computing the reliability of permutation and interval graphs, OptimalI-Intersection assignments for graphs: A linear programming approach, I-Colorings,I-Phasings, andI-Intersection assignments for graphs, and their applications, A Separator Theorem for Chordal Graphs, On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints, Unnamed Item, Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results, The Interval Count of a Graph, The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs, D-optimal statistical designs with restricted string property, Threshold tolerance graphs, On the tree representation of chordal graphs, Unnamed Item, Interval digraphs: An analogue of interval graphs, Algorithmic approach to the consecutive retrieval property, -constructibility of planar graphs, The bandwidth problem for graphs and matrices—a survey, Maximum Semiorders in Interval Orders, Extremal Values of the Interval Number of a Graph, Isomorphism Testing in Hookup Classes, Covering the edges with consecutive sets, Algorithms on circular-arc graphs, -constructibility of planar graphs, Lexbfs-orderings and powers of hhd-free graphs^∗, Computing the boxicity of a graph by covering its complement by cointerval graphs, Edge domination on bipartite permutation graphs and cotriangulated graphs, A note on lexicographic breadth first search for chordal graphs, Efficient parallel recognition of some circular arc graphs. II, Structure of concurrency, Counting endpoint sequences for interval orders and interval graphs, Basic derivations for subarrangements of Coxeter arrangements, Selected combinatorial problems of computational biology, Optimal weighing designs with a string property, Some aspects of perfect elimination orderings in chordal graphs, Separating subgraphs in k-trees: Cables and caterpillars, Circular representation problem on hypergraphs, Finding maximum cliques in arbitrary and in special graphs, Minimal triangulations of graphs: a survey, A vertex incremental approach for maintaining chordality, Minimal separators in \(P_4\)-sparse graphs, Lex M versus MCS-M, Inducing a blockmodel structure of two-mode binary data using seriation procedures, Alexandrov's inequality and conjectures on some Toeplitz matrices, Triangulated neighborhoods in even-hole-free graphs, Tree loop graphs, Recognizing graphs without asteroidal triples, Fair cost allocations under conflicts - a game-theoretic point of view -, Intersection representations of matrices by subtrees and unicycles on graphs, Counting the number of independent sets in chordal graphs, Bruhat order, smooth Schubert varieties, and hyperplane arrangements, On split-coloring problems, Recognizing edge clique graphs among interval graphs and probe interval graphs, Preemptive scheduling and antichain polyhedra, The neighbour-scattering number can be computed in polynomial time for interval graphs, Some remarks on interval graphs, Properties of (0,1)-matrices with no triangles, Decomposition by clique separators, Asymptotically optimal weighing designs with string property, Testing for class membership in multi-parent hierarchies, Fuzzy intersection graphs, Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs, Maximal chordal subgraphs, A class of lattices with Möbius function \(\pm 1,0\), Simplicial decompositions of graphs: A survey of applications, Algorithmic aspects of intersection graphs and representation hypergraphs, Subspaces with well-scaled frames, Extremal values of the interval number of a graph. II, Extremal values of the interval number of a graph, II, On minimal augmentation of a graph to obtain an interval graph, Complexity of representation of graphs by set systems, Inheritance principles for chordal graphs, Representations of graphs and networks (coding, layouts and embeddings), Some aspects of the semi-perfect elimination, Classes of bipartite graphs related to chordal graphs, An inertia formula for Hermitian matrices with sparse inverses, Norbert Wiener on the theory of measurement (1914, 1915, 1921), Optimal multiple interval assignments in frequency assignment and traffic phasing, Studies on hypergraphs. I: Hyperforests, Efficient parallel recognition of some circular arc graphs. I, An algorithm for testing chordality of graphs, A recognition algorithm for the intersection graphs of directed paths in directed trees, Information storage and retrieval - mathematical foundations. II: Combinatorial problems, Partition of a query set into minimal number of subsets having consecutive retrieval property, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, A note on perfect Gaussian elimination, Trivially perfect graphs, The circular dimension of a graph, The seriation problem and the travelling salesman problem, A recognition algorithm for the intersection graphs of paths in trees, Counting clique trees and computing perfect elimination schemes in parallel, Induced matchings, Phylogeny numbers, Optimal circular arc representations: Properties, recognition, and construction, An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs, Combinatorial optimization models for production scheduling in automated manufacturing systems, Minimal vertex separators of chordal graphs, On probe interval graphs, On the consecutive ones property, A generic disjunctive/conjunctive decomposition model for \(n\)-ary relations, The forbidden subgraph characterization of directed vertex graphs, Matrix sandwich problems, List \(T\)-colorings of graphs, The square of a chordal graph, Free hyperplane arrangements between \(A_{n-1}\) and \(B_ n\), A rounding algorithm for integer programs, A generalized insertion algorithm for the seriation problem, Periodic assignment and graph colouring, Algorithmic characterizations of interval orderd hypergraphs and applications, Compatibility between interval structures and partial orderings, The generating polynomial and Euler characteristic of intersection graphs, Finding minimum height elimination trees for interval graphs in polynomial time, Clique tree generalization and new subclasses of chordal graphs, New linear time algorithms for generating perfect elimination orderings of chordal graphs, Proper interval graphs and the guard problem, On properties of unit interval graphs with a perceptual motivation, Recognition of Robinsonian dissimilarities, Unit disk graph recognition is NP-hard, Satisfiability problems on intervals and unit intervals, Separability generalizes Dirac's theorem, Matching and multidimensional matching in chordal and strongly chordal graphs, PC trees and circular-ones arrangements., 2-role assignments on triangulated graphs., Recovering trees from well-separated multi-state characters., A selected tour of the theory of identification matrices