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)

• Pathwidth of Circular-Arc Graphs
• Graph spanners
• Totally-Balanced and Greedy Matrices
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
• Nonpreemptive scheduling of independent tasks with prespecified processor allocations
• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Preference structures and threshold models
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• An approximation result for a duo-processor task scheduling problem
• A parallel algorithm for solving the coloring problem on trapezoid graphs
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• An approximation algorithm for clustering graphs with dominating diametral path
• On-line algorithms for the dominating set problem
• An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
• Pattern matching for permutations
• Pattern matching for permutations
• On the SPANNING \(k\)-TREE problem
• Online scheduling with interval conflicts
• Bandwidth of chain graphs
• The recognition of geodetically connected graphs
• Vertex ranking of asteroidal triple-free graphs
• Consecutive retrieval property -- revisited
• On the performance of the first-fit coloring algorithm on permutation graphs
• Recognizing cographs and threshold graphs through a classification of their edges
• Recognizing \(i\)-triangulated graphs in \(O(mn)\) time
• Split graphs and Nordhaus-Gaddum graphs
• Circular convex bipartite graphs: feedback vertex sets
• Once more on matrogenic graphs
• Synthesizing partial orders given comparability information: Partitive sets and slack in critical path networks
• Minimal triangulations of graphs: a survey
• Transitive oriented 3 hypergraphs of cyclic orders
• Nordhaus-Gaddum theorem for the distinguishing chromatic number
• Trapezoid graphs and generalizations, geometry and algorithms
• The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
• Dominating sets for split and bipartite graphs
• Comparability graph augmentation for some multiprocessor scheduling problems
• Domination in convex and chordal bipartite graphs
• \(K_ i\)-covers. I: Complexity and polytopes
• On domination problems for permutation and other graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Trapezoid graphs and their coloring
• Dominating sets in perfect graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• Transitive closure for restricted classes of partial orders
• A parallel algorithm for minimum weighted colouring of triangulated graphs
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Generalized vertex covering in interval graphs
• Maximum \(k\)-covering of weighted transitive graphs with applications
• On the parameterized complexity of multiple-interval graph problems
• Resource allocation in bounded degree trees
• Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs
• Coloring perfect \((K_ 4\)-e)-free graphs
• A simple optimal parallel algorithm for the minimum coloring problem on interval graphs
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Parallel algorithms for permutation graphs
• Stability number of bull- and chair-free graphs
• On the feedback vertex set problem in permutation graphs
• Multidimensional scaling and threshold graphs
• Maximal chordal subgraphs
• Embedding planar graphs in four pages
• 2-role assignments on triangulated graphs.
• A charming class of perfectly orderable graphs
• The forbidden subgraph characterization of directed vertex graphs
• \(P_ 4\)-trees and substitution decomposition
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• On a graph partition problem with application to VLSI layout
• Quasi-planar graphs have a linear number of edges
• Recognizing clique graphs of directed and rooted path graphs
• On the pathwidth of chordal graphs
• Determining uni-connectivity in directed graphs
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Constant-time parallel recognition of split graphs
• Finding minimum height elimination trees for interval graphs in polynomial time
• Finding biconnected components in O(n) time for a class of graphs
• Efficient enumeration of all minimal separators in a graph
• The permutation-path coloring problem on trees.
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• Container ship stowage problem complexity and connection to the coloring of circle graphs
• Listing all potential maximal cliques of a graph
• Towards the reconstruction of posets
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Tree decompositions with small cost
• Parameterized complexity of vertex colouring
• Partitioning chordal graphs into independent sets and cliques
• Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
• Recognizing bull-free perfect graphs
• Partitions of graphs into one or two independent sets and cliques
• Perspectives of Monge properties in optimization
• Domination and total domination on asteroidal triple-free graphs
• A faster parallel connectivity algorithm on cographs
• A note on the complexity of locating-total domination in graphs
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• How hard is it to determine if a graph has a 2-role assignment?
• Boxicity and treewidth
• On the longest upsequence problem for permutations
• Threshold Dimension of Graphs
• A linear time algorithm to construct a tree 4-spanner on trapezoid graphs
• Characterizing –partitionable Cographs

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)