Algorithmic aspects of intersection graphs and representation hypergraphs
From MaRDI portal
Publication:1119661
DOI10.1007/BF01864170zbMath0671.05034MaRDI QIDQ1119661
Publication date: 1988
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)
Related Items (7)
Dually chordal graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Approximation algorithms for intersection graphs ⋮ Difference graphs ⋮ A type of algebraic structure related to sets of intervals ⋮ Matrix sandwich problems ⋮ Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The edge intersection graphs of paths in a tree
- Chronological orderings of interval graphs
- Tolerance graphs
- Circular representation problem on hypergraphs
- An O(qn) algorithm to q-color a proper family of circular arcs
- Edge and vertex intersection of paths in a tree
- Interval graphs and interval orders
- Intersection graphs of paths in a tree
- An application of vertex packing to data analysis in the evaluation of pavement deterioration
- The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph
- Hypergraphes de chaînes d'aretes d'un arbre
- Comparability graphs and intersection graphs
- Comparability graphs and a new matroid
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- A note on perfect Gaussian elimination
- Hypergraphes arbores
- A recognition algorithm for the intersection graphs of paths in trees
- A characterisation of rigid circuit graphs
- Incidence matrices and interval graphs
- Triangulated graphs and the elimination process
- Matrix characterizations of circular-arc graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Structure theorems for some circular-arc graphs
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- Syntactic Characterization of Tree Database Schemas
- An Algorithm for Determining Whether a Given Binary Matroid is Graphic
- I-Colorings,I-Phasings, andI-Intersection assignments for graphs, and their applications
- Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- The Complexity of the Partial Order Dimension Problem
- Counting Interval Graphs
- An algorithm for constructing edge-trees from hypergraphs
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- On Comparability and Permutation Graphs
- Stability in circular arc graphs
- An Efficient Test for Circular-Arc Graphs
- Efficient algorithms for interval graphs and circular-arc graphs
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- The Complexity of Coloring Circular Arcs and Chords
- Containment Graphs, Posets, and Related Classes of Graphs
- Algorithms on circular-arc graphs
- Coloring a Family of Circular Arcs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Recognizing circle graphs in polynomial time
- Characterizing circular-arc graphs
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Permutation Graphs and Transitive Graphs
- A Characterization of Comparability Graphs and of Interval Graphs
- Partially Ordered Sets
This page was built for publication: Algorithmic aspects of intersection graphs and representation hypergraphs
