Algorithmic aspects of intersection graphs and representation hypergraphs
type: Item
instance of: scholarly article
title: Algorithmic aspects of intersection graphs and representation hypergraphs
zbMATH Open document ID: 0671.05034
DOI: 10.1007/BF01864170
author: Martin Charles Golumbic
published in: Graphs and Combinatorics
publication date: 1988-01-01T00:00:00Z
review text: This paper presents a survey about algorithms for common graph theory questions for different classes of intersection graphs. A graph is an intersection graph if there is a one-to-one correspondence between its vertices and a family of sets (intervals on the line, boxes in n-space, etc.) such that two vertices are adjacent if and only if the corresponding objects overlap. Some equivalences of problems are given and some problems are restated in hypergraph terminology.
reviewed by: Alan C. Tucker
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4097411
zbMATH Keywords: intersection graphs
MaRDI profile type: Publication
cites work: On the Desirability of Acyclic Database Schemes
cites work: Q5668821
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Q3708048
cites work: A characterisation of rigid circuit graphs
cites work: The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph
cites work: Q3222876
cites work: Partially Ordered Sets
cites work: Permutation Graphs and Transitive Graphs
cites work: Degrees of acyclicity for hypergraphs and relational database schemes
cites work: Q3309102
cites work: Interval graphs and interval orders
cites work: Hypergraphes arbores
cites work: Hypergraphes de chaînes d'aretes d'un arbre
cites work: Incidence matrices and interval graphs
cites work: Recognizing circle graphs in polynomial time
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: An application of vertex packing to data analysis in the evaluation of pavement deterioration
cites work: Algorithms on circular-arc graphs
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: A recognition algorithm for the intersection graphs of paths in trees
cites work: An algorithm for constructing edge-trees from hypergraphs
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Comparability graphs and a new matroid
cites work: A note on perfect Gaussian elimination
cites work: Q3328583
cites work: Q3221420
cites work: Q3914453
cites work: Stability in circular arc graphs
cites work: The edge intersection graphs of paths in a tree
cites work: Edge and vertex intersection of paths in a tree
cites work: Q3322150
cites work: Tolerance graphs
cites work: Comparability graphs and intersection graphs
cites work: Containment Graphs, Posets, and Related Classes of Graphs
cites work: Syntactic Characterization of Tree Database Schemas
cites work: Efficient algorithms for interval graphs and circular-arc graphs
cites work: Counting Interval Graphs
cites work: Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
cites work: Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
cites work: Q3668890
cites work: Intersection graphs of paths in a tree
cites work: I-Colorings,I-Phasings, andI-Intersection assignments for graphs, and their applications
cites work: An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
cites work: Transitive Orientation of Graphs and Identification of Permutation Graphs
cites work: Q3694703
cites work: Circular representation problem on hypergraphs
cites work: Q4138414
cites work: Triangulated graphs and the elimination process
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Chronological orderings of interval graphs
cites work: On Comparability and Permutation Graphs
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: An O(qn) algorithm to q-color a proper family of circular arcs
cites work: Characterizing circular-arc graphs
cites work: Matrix characterizations of circular-arc graphs
cites work: Structure theorems for some circular-arc graphs
cites work: Coloring a Family of Circular Arcs
cites work: An Efficient Test for Circular-Arc Graphs
cites work: An Algorithm for Determining Whether a Given Binary Matroid is Graphic
cites work: The Complexity of the Partial Order Dimension Problem
description: scientific article; zbMATH DE number 4097411