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)

• How to use the minimal separators of a graph for its chordal triangulation
• An efficient algorithm to solve the conditional covering problem on trapezoid graphs
• Maximum weightk-independent set problem on permutation graphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Title not available (Why is that?)
• Optimization problems in multiple subtree graphs
• Powers of cycles, powers of paths, and distance graphs
• Minimum vertex cover in rectangle graphs
• Random threshold digraphs
• Organizing the atoms of the clique separator decomposition into an atom tree
• Partial multicovering and the \(d\)-consecutive ones property
• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• Using fractional primal-dual to schedule split intervals with demands
• Subtree and substar intersection numbers
• The interlace polynomial of a graph
• On the Max Coloring Problem
• Chronological orderings of interval graphs
• Monotonicity of the mean order of subtrees
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Tangent circle graphs and `orders'
• On conditional covering problem
• Boxicity of circular arc graphs
• Chordal bipartite graphs with high boxicity
• The maximum edit distance from hereditary graph properties
• Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Trimming weighted graphs of bounded treewidth
• On a problem concerning tolerance graphs
• On the max coloring problem
• String graphs and incomparability graphs
• Hardness of edge-modification problems
• On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
• Tolerance graphs
• Packing and covering a tree by subtrees
• The treewidth and pathwidth of hypercubes
• Online variable-sized bin packing with conflicts
• Branchwidth of chordal graphs
• Boxicity and cubicity of asteroidal triple free graphs
• A linear time recognition algorithm for proper interval graphs
• An interval digraph in relation to its associated bipartite graph
• An efficient algorithm to find next-to-shortest path on permutation graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Minimal indecomposable graphs
• On hypergraph acyclicity and graph chordality
• Bipartite dimensions and bipartite degrees of graphs
• On Hadwiger's number---A problem of the Nordhaus-Gaddum type
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Euler circuits and DNA sequencing by hybridization
• Intersection graphs of concatenable subtrees of graphs
• Some remarks on interval graphs
• Clique-perfectness of claw-free planar graphs
• Homogeneously representable interval graphs
• Separability generalizes Dirac's theorem
• On finding an empty staircase polygon of largest area (width) in a planar point-set
• Chordal embeddings of planar graphs
• A note on odd/even cycles
• Reasoning about qualitative temporal information
• A trichotomy: Interactions of factors prolonging sequential and concurrent mental processes in stochastic discrete mental (PERT) networks
• Partitioning a weighted partial order
• On the clique-transversal number of chordal graphs
• On the computational complexity of strong edge coloring
• Computing branchwidth via efficient triangulations and blocks
• Semidefinite programming in combinatorial optimization
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Linear-time modular decomposition of directed graphs
• An efficient algorithm for finding a two-pair, and its applications
• Geometrical embeddings of graphs
• On the number of vertices belonging to all maximum stable sets of a graph
• Formal systems for gene assembly in ciliates.
• Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
• Relaxations of vertex packing
• On the two-phase method for preemptive scheduling
• Centers of chordal graphs
• Equicovering matroids by distinct bases
• Hamiltonian powers in threshold and arborescent comparability graphs
• Interval-like graphs and digraphs
• A graph colouring model for assigning a heterogeneous workforce to a given schedule
• Paths in interval graphs and circular arc graphs
• Bin-packing and matchings in threshold graphs
• Triangulating multitolerance graphs
• Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Adjusted interval digraphs
• Modeling and solving a crew assignment problem in air transportation
• The edge-orientation problem and some of its variants on weighted graphs
• On some simplicial elimination schemes for chordal graphs
• Overlap number of graphs
• On weights and quotas for weighted majority voting games
• Track assignment
• The Roberts characterization of proper and unit interval graphs
• The \(k\)-Track assignment problem on partial orders
• On the structure of contractible vertex pairs in chordal graphs
• A simple linear-time algorithm for computing the center of an interval graph
• A reliability-improving graph transformation with applications to network reliability
• Transforming trees by successive local complementations
• Extremal interval graphs
• The Interval Count of a Graph
• Minimizer graphs for a class of extremal problems
• Minimal ordered triangulations of surfaces

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)