Incidence matrices and interval graphs

DOI10.2140/PJM.1965.15.835zbMath0132.21001OpenAlexW2089465933WikidataQ55952668 ScholiaQ55952668MaRDI QIDQ2395457

D. R. Fulkerson, Oliver Gross

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 (only showing first 100 items - show all)

Linear-Time Generation of Random Chordal Graphs ⋮ Efficient parallel algorithms for bipartite permutation graphs ⋮ Characterizing circular-arc graphs ⋮ Reconstruction of Interval Graphs ⋮ A simple linear time algorithm for triangulating three-colored graphs ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ Extending partial representations of circular-arc graphs ⋮ A Model for Birdwatching and other Chronological Sampling Activities ⋮ Linear optimization over homogeneous matrix cones ⋮ Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations ⋮ Coloring rings ⋮ On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs ⋮ Minimum cost flow problem with conflicts ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ On the edge‐biclique graph and the iterated edge‐biclique operator ⋮ Exponential neighborhood search for consecutive block minimization ⋮ Coloring \((4K_1,C_4,C_6)\)-free graphs ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ Isabelle formalisation of original representation theorems ⋮ MAT-free graphic arrangements and a characterization of strongly chordal graphs by edge-labeling ⋮ On semi-transitive orientability of split graphs ⋮ Cycle intersection in spanning trees: a shorter proof of a conjecture and applications ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ The parallel complexity of elimination ordering procedures ⋮ Dually chordal graphs ⋮ On characterizing proper max-point-tolerance graphs ⋮ Finding biclique partitions of co-chordal graphs ⋮ Combinatorial Generation via Permutation Languages. V. Acyclic Orientations ⋮ Partial orders of dimension 2 ⋮ Localization in 1D non-parametric latent space models from pairwise affinities ⋮ On 3-degree 4-chordal graphs ⋮ Independence polynomials and hypergeometric series ⋮ Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC ⋮ On domination elimination orderings and domination graphs ⋮ Dominoes ⋮ Algorithms for a maximum clique and a maximum independent set of a circle graph ⋮ Min-Orderable Digraphs ⋮ Hardness results of global Roman domination in graphs ⋮ Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension ⋮ Hardness results of global total \(k\)-domination problem in graphs ⋮ Consecutive ones matrices for multi-dimensional orthogonal packing problems ⋮ Analysis of upper bounds for the pallet loading problem ⋮ Strong spatial mixing in homomorphism spaces ⋮ Totally positive matrices and totally positive hypergraphs ⋮ Intersection graphs of non-crossing paths ⋮ Biclique graphs and biclique matrices ⋮ Robust spectrum allocation in elastic flexgrid optical networks: complexity and formulations ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ On the complexity of alpha conversion ⋮ On Physical Mapping and the consecutive ones property for sparse matrices ⋮ Minimizing phylogenetic number to find good evolutionary trees ⋮ On \(H\)-topological intersection graphs ⋮ Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs ⋮ Two strikes against perfect phylogeny ⋮ Complexity and algorithms for semipaired domination in graphs ⋮ Poincaré-Hopf inequalities ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs ⋮ Contracting chordal graphs and bipartite graphs to paths and trees ⋮ Unnamed Item ⋮ The homotopy theory of polyhedral products associated with flag complexes ⋮ Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited ⋮ Linear-Time Recognition of Probe Interval Graphs ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Hamiltonian Chordal Graphs are not Cycle Extendable ⋮ A separator-based method for generating weakly chordal graphs ⋮ Unnamed Item ⋮ On the maximum number of edges in chordal graphs of bounded degree and matching number ⋮ A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs ⋮ Customizable Contraction Hierarchies ⋮ 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 ⋮ Long paths and toughness of \(k\)-trees and chordal planar graphs ⋮ Signed graphs and the freeness of the Weyl subarrangements of type \(B_\ell\) ⋮ 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 ⋮ Testing for class membership in multi-parent hierarchies ⋮ Fuzzy intersection graphs ⋮ Proper interval graphs and the guard problem ⋮ 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\) ⋮ Graph extremities defined by search algorithms ⋮ Computing a clique tree with the algorithm maximal label search ⋮ Simplicial decompositions of graphs: A survey of applications ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ On properties of unit interval graphs with a perceptual motivation ⋮ Subspaces with well-scaled frames ⋮ Recognition of Robinsonian dissimilarities ⋮ Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs ⋮ Unit disk graph recognition is NP-hard ⋮ Satisfiability problems on intervals and unit intervals ⋮ On the \(b\)-continuity of the lexicographic product of graphs ⋮ Separability generalizes Dirac's theorem

This page was built for publication: Incidence matrices and interval graphs