scientific article; zbMATH DE number 3859178
From MaRDI portal
Publication:3328583
zbMATH Open0541.05054MaRDI QIDQ3328583FDOQ3328583
Authors: Martin Charles Golumbic 
Publication date: 1980
Title of this publication is not available (Why is that?)
Recommendations
split graphperfect graphthreshold graphefficient algorithminterval graphpermutation graphcomparability graphtriangulated graph
Searching and sorting (68P10) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99) Algorithms in computer science (68W99)
Cited In (only showing first 100 items - show all)
- Algorithmic aspects of clique-transversal and clique-independent sets
- Localized and compact data-structure for comparability graphs
- On the chromatic number of multiple interval graphs and overlap graphs
- Maximum weight independent sets in hole- and co-chair-free graphs
- On independent vertex sets in subclasses of apple-free graphs
- Approximation of RNA multiple structural alignment
- Precoloring extension. I: Interval graphs
- Independence and domination in polygon graphs
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs
- Covering and coloring polygon-circle graphs
- Threshold hypergraphs
- Labeling algorithms for domination problems in sun-free chordal graphs
- Some aspects of the semi-perfect elimination
- Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
- On a property of minimal triangulations
- Minimal interval completion through graph exploration
- A remark on perfect Gaussian elimination of symmetric matrices
- NP-completeness results for edge modification problems
- Approximating the minimum clique cover and other hard problems in subtree filament graphs
- Bandwidth of bipartite permutation graphs in polynomial time
- The neighborhood inclusion structure of a graph
- Circular-arc graphs with clique cover number two
- Interval graphs and maps of DNA
- Finding large holes
- Recognizing quasi-triangulated graphs.
- Split and balanced colorings of complete graphs
- The polytope of degree sequences of hypergraphs
- Characterizations and algorithmic applications of chordal graph embeddings
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- On clique-complete graphs
- Clique partitioning of interval graphs with submodular costs on the cliques
- Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
- On the semi-perfect elimination
- Recognition of perfect elimination bipartite graphs
- An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
- On the structure of trapezoid graphs
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Retracts of products of chordal graphs
- Approximating minimum cocolorings.
- Parameterized complexity of finding subgraphs with hereditary properties.
- Triangulating graphs without asteroidal triples
- Partitioning permutations into increasing and decreasing subsequences
- A Note on k-Colorability of P 5-Free Graphs
- Threshold tolerance graphs
- Some classes of perfectly orderable graphs
- On the homogeneous representation of interval graphs
- A simple nc recognition algorithm for welsh-powell opposition graphs
- Formulas for counting acyclic digraph Markov equivalence classes
- Minimal comparability completions of arbitrary graphs
- An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
- Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
- Backbone colorings for graphs: Tree and path backbones
- The approximation of maximum subgraph problems
- On the existence of convex decompositions of partially separable functions
- Simple heuristics for unit disk graphs
- Characterizing width two for variants of treewidth
- Complexity of coloring graphs without paths and cycles
- On recognition of threshold tolerance graphs and their complements
- Treewidth and pathwidth parameterized by the vertex cover number
- Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
- Permutation bigraphs and interval containments
- On critical circle homeomorphisms
- Certifying algorithms
- Space graphs and sphericity
- A ZONAL ALGORITHM FOR CLUSTERING AN HOC NETWORKS
- A linear-time algorithm for proper interval graph recognition
- Two remarks on circular arc graphs
- On distance-3 matchings and induced matchings
- On the sphericity and cubicity of graphs
- Sphere-of-influence graphs using the sup-norm
- Approximation algorithms for time constrained scheduling
- Girth and treewidth
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- On sources in comparability graphs, with applications
- Finding maximum cliques in arbitrary and in special graphs
- List homomorphisms to reflexive graphs
- Intersection dimensions of graph classes
- \(r\)-dominating cliques in graphs with hypertree structure
- Classes of bipartite graphs related to chordal graphs
- Efficient parallel recognition of some circular arc graphs. I
- Induced matchings in intersection graphs.
- Obstructions to partitions of chordal graphs
- Precoloring Extension III: Classes of Perfect Graphs
- Graphs whose adjacency matrices have rank equal to the number of distinct nonzero rows
- Fixed-parameter tractability of treewidth and pathwidth
- Neighborhood subtree tolerance graphs
- Two strikes against perfect phylogeny
- On Injective Colourings of Chordal Graphs
- About skew partitions in minimal imperfect graphs
- Covering and coloring problems for relatives of intervals
- Unified all-pairs shortest path algorithms in the chordal hierarchy
- Permuting matrices to avoid forbidden submatrices
- List matrix partitions of chordal graphs
- Representing digraphs using intervals or circular arcs
- Two characterisations of the minimal triangulations of permutation graphs
- The polytope of degree sequences
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3328583)
