scientific article; zbMATH DE number 3859178

zbMATH Open0541.05054MaRDI QIDQ3328583FDOQ3328583

Authors: Martin Charles Golumbic 

Publication date: 1980

Title of this publication is not available (Why is that?)

Recommendations

• Algorithmic graph theory and perfect graphs
• Progress on perfect graphs
• scientific article; zbMATH DE number 108587
• scientific article; zbMATH DE number 3851153
• Perfect graphs

zbMATH Keywords

split graphperfect graphthreshold graphefficient algorithminterval graphpermutation graphcomparability graphtriangulated graph

Mathematics Subject Classification ID

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)

• Exact algorithms for intervalizing coloured graphs
• Nonparametric estimation of the bivariate CDF for arbitrarily censored data
• Schur products and matrix completions
• Title not available (Why is that?)
• Probability propagation
• On the minimum and maximum selective graph coloring problems in some graph classes
• An optimal algorithm to recognize Robinsonian dissimilarities
• The maximum clique problem
• TS\(^2\)PACK: A two-level tabu search for the three-dimensional bin packing problem
• The coloring problem for classes with two small obstructions
• Quasi‐transitive digraphs
• On intervalizing \(k\)-colored graphs for DNA physical mapping
• Simple linear time recognition of unit interval graphs
• A hybrid tractable class for non-binary CSPs
• Colouring, constraint satisfaction, and complexity
• Counting and enumerating independent sets with applications to combinatorial optimization problems
• The edge intersection graphs of paths in a tree
• The Laplacian energy of threshold graphs and majorization
• Diameter determination on restricted graph families
• Heuristics for the network design problem with connectivity requirements
• Two poset polytopes
• Augmenting approach for some maximum set problems
• Two topics in tree inference: locating a phonological network effect in immediate recall and arborescence partitive set form
• Linear algorithm for optimal path cover problem on interval graphs
• A characterization of graphs with rank 4
• The square of a block graph
• The complexity of querying indefinite data about linearly ordered domains
• Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs
• Finding Hamiltonian circuits in proper interval graphs
• Edge and vertex intersection of paths in a tree
• Triangulated edge intersection graphs of paths in a tree
• Clustering and domination in perfect graphs
• Rankings of graphs
• Intersection graphs of paths in a tree
• Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
• Scheduling jobs with fixed start and end times
• Subgraph isomorphism in graph classes
• Resolutions of Stanley-Reisner rings and Alexander duality
• Complement reducible graphs
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Comparability graphs and intersection graphs
• Unit disk graphs
• The complexity of reconstructing trees from qualitative characters and subtrees
• A partial k-arboretum of graphs with bounded treewidth
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Finding a maximum independent set in a permutation graph
• Modular decomposition and transitive orientation
• Complexity of conditional colorability of graphs
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Recognition of Robinsonian dissimilarities
• Equistable chordal graphs
• Broken circuit complexes: Factorizations and generalizations
• \(T\)-colorings of graphs: recent results and open problems
• Tree inference with factors selectively influencing processes in a processing tree
• Characterizations of strongly chordal graphs
• Interval graphs and interval orders
• Bipartite permutation graphs
• Bridged graphs and geodesic convexity
• Intersection graphs of halflines and halfplanes
• The \(k\)-regular induced subgraph problem
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Constructing a stochastic critical path network given the slacks: Representation
• Optimal multiple interval assignments in frequency assignment and traffic phasing
• On the \(k\)-coloring of intervals
• A graph-theoretic method for organizing overlapping clusters into trees, multiple trees, or extended trees
• Induced matchings
• A good characterization of squares of strongly chordal split graphs
• A branch and bound algorithm for the resource-constrained project scheduling problem
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• On some optimization problems on \(k\)-trees and partial \(k\)-trees
• Graphs of some CAT(0) complexes
• Linear recognition of pseudo-split graphs
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Tree spanners on chordal graphs: complexity and algorithms
• On edge perfectness and classes of bipartite graphs
• A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
• Recognizing Helly edge-path-tree graphs and their clique graphs
• Optimal greedy algorithms for indifference graphs
• HAMILTONian circuits in chordal bipartite graphs
• Complexity of finding graph roots with girth conditions
• The maximum vertex coverage problem on bipartite graphs
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Equistable distance-hereditary graphs
• Geodeticity of the contour of chordal graphs
• Self-clique Helly circular-arc graphs
• One-way and round-trip center location problems
• TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
• Interval digraphs: An analogue of interval graphs
• A survey on labeling graphs with a condition at distance two
• On the proper intervalization of colored caterpillar trees
• Large Induced Subgraphs via Triangulations and CMSO
• Subgraphs and well‐quasi‐ordering
• I-Colorings,I-Phasings, andI-Intersection assignments for graphs, and their applications
• On the tree representation of chordal graphs
• Equistable graphs
• Interval scheduling: A survey
• The Complexity of the Partial Order Dimension Problem
• The completely positive and doubly nonnegative completion problems
• Efficient algorithms for centers and medians in interval and circular-arc graphs

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)