scientific article

Publication date: 1980

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

split graph comparability graph perfect graph interval graph efficient algorithm threshold graph permutation graph triangulated 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)

Related Items (only showing first 100 items - show all)

Bipartite dimensions and bipartite degrees of graphs ⋮ Some properties of minimal imperfect graphs ⋮ List homomorphisms to reflexive graphs ⋮ Complement reducible graphs ⋮ Optimal packing and covering in the plane are NP-complete ⋮ Restricted thresholds for interval orders: A case of nonaxiomatizability by a universal sentence ⋮ An application of vertex packing to data analysis in the evaluation of pavement deterioration ⋮ Coloring graphs with stable cutsets ⋮ A solution of the Sperner-Erdős problem ⋮ Comparability graphs and intersection graphs ⋮ Inheritance principles for chordal graphs ⋮ Chordal graphs and upper irredundance, upper domination and independence ⋮ Dominating sets in perfect graphs ⋮ Unit disk graphs ⋮ Permutation graphs: Connected domination and Steiner trees ⋮ On the use of augmenting chains in chain packings ⋮ Short-chorded and perfect graphs ⋮ Broken circuit complexes: Factorizations and generalizations ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Lifting positive elements in \(C^*\)-algebras ⋮ Intersection properties of graphs ⋮ Some aspects of the semi-perfect elimination ⋮ On the complexity of testing for odd holes and induced odd paths ⋮ \((i,j)\) competition graphs ⋮ Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths ⋮ Classes of bipartite graphs related to chordal graphs ⋮ Some properties of graph centroids ⋮ Edge-clique graphs ⋮ Centers of chordal graphs ⋮ Cycle-free partial orders and chordal comparability graphs ⋮ Transitive closure for restricted classes of partial orders ⋮ Finding large holes ⋮ On a unique tree representation for \(P_ 4\)-extendible graphs ⋮ A condition for a family of triangles to be orientable to a cyclic order ⋮ \(T\)-colorings of graphs: recent results and open problems ⋮ The symbiotic relationship of combinatorics and matrix theory ⋮ An inertia formula for Hermitian matrices with sparse inverses ⋮ Single step graph search problem ⋮ Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs ⋮ New clique and independent set algorithms for circle graphs ⋮ An optimal algorithm for finding dominating cycles in circular-arc graphs ⋮ Stability number and chromatic number of tolerance graphs ⋮ Completion of operator partial matrices associated with chordal graphs ⋮ Connected domination and Steiner set on weighted permutation graphs ⋮ Norbert Wiener on the theory of measurement (1914, 1915, 1921) ⋮ A charming class of perfectly orderable graphs ⋮ A parallel algorithm for minimum weighted colouring of triangulated graphs ⋮ One-step completions of Hermitian partial matrices with minimal negative signature ⋮ Generalized transitive tournaments and doubly stochastic matrices ⋮ Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs ⋮ An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model ⋮ The weighted maximum independent set problem in permutation graphs ⋮ Constructing a stochastic critical path network given the slacks: Representation ⋮ On Hadwiger's number---A problem of the Nordhaus-Gaddum type ⋮ Graphs and topologies on discrete sets ⋮ Optimal parallel algorithms for finding cut vertices and bridges of interval graphs ⋮ Precoloring extension. I: Interval graphs ⋮ Generalized vertex covering in interval graphs ⋮ A new characterization of proper interval graphs ⋮ On a graph partition problem with application to VLSI layout ⋮ An efficient algorithm for finding a maximum weight 2-independent set on interval graphs ⋮ Hamiltonian cycle is polynomial on cocomparability graphs ⋮ \(P_ 4\)-trees and substitution decomposition ⋮ The complexity of coloring games on perfect graphs ⋮ The complexity of reconstructing trees from qualitative characters and subtrees ⋮ Reasoning about qualitative temporal information ⋮ Maximum \(k\)-covering of weighted transitive graphs with applications ⋮ On sources in comparability graphs, with applications ⋮ Optimal multiple interval assignments in frequency assignment and traffic phasing ⋮ Circular permutation graph family with applications ⋮ Stability number of bull- and chair-free graphs ⋮ Studies on hypergraphs. I: Hyperforests ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs ⋮ Paths in interval graphs and circular arc graphs ⋮ A chordal preconditioner for large-scale optimization ⋮ Induced matchings ⋮ A remark on perfect Gaussian elimination of symmetric matrices ⋮ Optimal parallel algorithms on circular-arc graphs ⋮ Chordal graph models of contingency tables ⋮ Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems ⋮ A graph colouring model for assigning a heterogeneous workforce to a given schedule ⋮ Solving the weighted efficient edge domination problem on bipartite permutation graphs ⋮ Phylogeny numbers ⋮ Optimal circular arc representations: Properties, recognition, and construction ⋮ An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Triangulating graphs with few \(P_4\)'s ⋮ Partial and perfect path covers of cographs ⋮ Minimal vertex separators of chordal graphs ⋮ On probe interval graphs ⋮ Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ Construction of a simple elimination scheme for a chordal comparability graph in linear time ⋮ Arithmetical semigroups related to trees and polyhedra ⋮ The bandwidth of the complement of a \(k\)-tree ⋮ Recognizing clique graphs of directed and rooted path graphs ⋮ \(P_4\)-domination in minimal imperfect graphs ⋮ Resolutions of Stanley-Reisner rings and Alexander duality ⋮ Heuristics for multimode scheduling problems with dedicated resources

This page was built for publication: