Algorithmic aspects of intersection graphs and representation hypergraphs

DOI10.1007/BF01864170MaRDI QIDQ1119661zbMATH OpenFDO

Authors Martin Charles Golumbic

Publication date 1988

Published in Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

intersection graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Hypergraphs (05C65) Graph theory (05C99)

Recommendations

• Simple Geometrical Intersection Graphs
• Efficient graph representations
• Tractabilities and intractabilities on geometric intersection graphs
• Characterizing intersection classes of graphs
• Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph

Cites work

• scientific article; zbMATH DE number 3888924 (Why is no real title available?)
• scientific article; zbMATH DE number 3889566 (Why is no real title available?)
• scientific article; zbMATH DE number 3839362 (Why is no real title available?)
• scientific article; zbMATH DE number 3853140 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3823168 (Why is no real title available?)
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 3933116 (Why is no real title available?)
• scientific article; zbMATH DE number 3725718 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• A characterisation of rigid circuit graphs
• A note on perfect Gaussian elimination
• A recognition algorithm for the intersection graphs of paths in trees
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms on circular-arc graphs
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• An Efficient Test for Circular-Arc Graphs
• An O(qn) algorithm to q-color a proper family of circular arcs
• An algorithm for constructing edge-trees from hypergraphs
• An application of vertex packing to data analysis in the evaluation of pavement deterioration
• Characterizing circular-arc graphs
• Chronological orderings of interval graphs
• Circular representation problem on hypergraphs
• Coloring a Family of Circular Arcs
• Comparability graphs and a new matroid
• Comparability graphs and intersection graphs
• Containment Graphs, Posets, and Related Classes of Graphs
• Counting Interval Graphs
• Degrees of acyclicity for hypergraphs and relational database schemes
• Edge and vertex intersection of paths in a tree
• Efficient algorithms for interval graphs and circular-arc graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Hypergraphes arbores
• Hypergraphes de chaînes d'aretes d'un arbre
• I-Colorings,I-Phasings, andI-Intersection assignments for graphs, and their applications
• Incidence matrices and interval graphs
• Intersection graphs of paths in a tree
• Interval graphs and interval orders
• Matrix characterizations of circular-arc graphs
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• On Comparability and Permutation Graphs
• On the Desirability of Acyclic Database Schemes
• Partially Ordered Sets
• Permutation Graphs and Transitive Graphs
• Recognizing circle graphs in polynomial time
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Stability in circular arc graphs
• Structure theorems for some circular-arc graphs
• Syntactic Characterization of Tree Database Schemas
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Complexity of Coloring Circular Arcs and Chords
• The Complexity of the Partial Order Dimension Problem
• The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph
• The edge intersection graphs of paths in a tree
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Tolerance graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Triangulated graphs and the elimination process

Cited in

(17)

• Difference graphs
• Simple Geometrical Intersection Graphs
• Multiaspect graphs: algebraic representation and algorithms
• Matrix sandwich problems
• On the complexity of directed intersection representation of DAGs
• Efficient graph representations
• The representation of multi-hypergraphs by set intersections
• Can they cross? and how? (the hitchhiker's guide to the universe of geometric intersection graphs)
• scientific article; zbMATH DE number 1185600 (Why is no real title available?)
• Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets
• Dually chordal graphs
• Approximation algorithms for intersection graphs
• Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
• Hyperideal-based intersection graphs
• Directed Intersection Representations and the Information Content of Digraphs
• A type of algebraic structure related to sets of intervals
• Representations of graphs and networks (coding, layouts and embeddings)

This page was built for publication: Algorithmic aspects of intersection graphs and representation hypergraphs

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