Algorithmic aspects of intersection graphs and representation hypergraphs
From MaRDI portal
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.
Recommendations
Cites work
- A characterisation of rigid circuit graphs
- A Characterization of Comparability Graphs and of Interval 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 constructing edge-trees from hypergraphs
- An Algorithm for Determining Whether a Given Binary Matroid is Graphic
- An application of vertex packing to data analysis in the evaluation of pavement deterioration
- An Efficient Test for Circular-Arc Graphs
- An O(qn) algorithm to q-color a proper family of circular arcs
- 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
- 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?)
- 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 asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph
- The Complexity of Coloring Circular Arcs and Chords
- The Complexity of the Partial Order Dimension Problem
- 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
(20)- Representations of graphs and networks (coding, layouts and embeddings)
- Matrix sandwich problems
- Efficient graph representations
- Multiaspect graphs: algebraic representation and algorithms
- On the complexity of directed intersection representation of DAGs
- A type of algebraic structure related to sets of intervals
- Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets
- The representation of multi-hypergraphs by set intersections
- scientific article; zbMATH DE number 1185600 (Why is no real title available?)
- Approximation algorithms for intersection graphs
- scientific article; zbMATH DE number 861316 (Why is no real title available?)
- Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
- Directed Intersection Representations and the Information Content of Digraphs
- Can they cross? and how? (the hitchhiker's guide to the universe of geometric intersection graphs)
- Simple Geometrical Intersection Graphs
- Difference graphs
- Hyperideal-based intersection graphs
- Dually chordal graphs
- Simultaneous contact representations of planar graphs
- Quasi-transitive mixed graphs and undirected squares of oriented graphs
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)
