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)
- Batch processing with interval graph compatibilities between tasks
- Toughness in graphs -- a survey
- Algorithms for clique-independent sets on subclasses of circular-arc graphs
- Identifying phylogenetic trees
- A sequential algorithm for finding a maximum weightK-independent set on interval graphs
- Matrix partitions of perfect graphs
- An exact method for graph coloring
- Interval scheduling on identical machines
- Online Bounded Coloring of Permutation and Overlap Graphs
- Extermal positive semidefinite matrices with given sparsity pattern
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Dominating cliques in distance-hereditary graphs
- Parallel algorithm for cograph recognition with applications
- Vertex ranking of asteroidal triple-free graphs
- Complexity of approximating the oriented diameter of chordal graphs
- An optimal parallel algorithm for computing cut vertices and blocks on interval graphs
- The algorithmic complexity of mixed domination in graphs
- An optimal parallel algorithm to construct a tree 3-spanner on interval graphs
- Embedding of cycles and wheels into arbitrary trees
- Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
- A linear time algorithm for finding all hinge vertices of a permutation graph
- Trapezoid graphs and generalizations, geometry and algorithms
- Dominating cliques in graphs
- Complexity classification of some edge modification problems
- On algorithms for (\(P_5\), gem)-free graphs
- Parameterized coloring problems on chordal graphs
- Inverse chromatic number problems in interval and permutation graphs
- The weighted perfect domination problem
- Asteroidal triple-free graphs
- Chordal deletion is fixed-parameter tractable
- Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs
- Chronological rectangle digraphs
- On containment graphs of paths in a tree
- Tri-connectivity augmentation in trees
- Largest chordal and interval subgraphs faster than \(2^n\)
- Notes on a theorem of Naji
- The off-line group seat reservation problem
- Bipartite permutation graphs with application to the minimum buffer size problem
- Treewidth computations. I: Upper bounds
- Recognition and characterization of chronological interval digraphs
- Recognizing locally equivalent graphs
- A survey of the algorithmic aspects of modular decomposition
- On the non-unit count of interval graphs
- Clique graphs of time graphs
- On the complexity of the positive semidefinite zero forcing number
- Möbius functions and confluent semi-commutations
- Colourings, homomorphisms, and partitions of transitive digraphs
- An evolution of interval graphs
- The pathwidth and treewidth of cographs
- A tutorial on the use of graph coloring for some problems in robotics
- Some results about the interval number of a graph
- Positive semidefinite matrices with a given sparsity pattern
- Random interval graphs
- Edge-clique graphs
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- Norbert Wiener on the theory of measurement (1914, 1915, 1921)
- Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
- Partition-distance: A problem and class of perfect graphs arising in clustering
- An optimal greedy heuristic to color interval graphs
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Weighted efficient domination problem on some perfect graphs
- Reconnaissance des graphes de cordes
- Finding Hamiltonian circuits in interval graphs
- Optimal channel allocation for several types of cellular radio networks
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- On embedding graphs in trees
- Graphic presentations of isotropic systems
- Reducing prime graphs and recognizing circle graphs
- On the unit interval number of a graph
- Digraph matrix partitions and trigraph homomorphisms
- Decomposition of balanced matrices
- Perfect edge domination and efficient edge domination in graphs
- Covering orthogonal polygons with star polygons: The perfect graph approach
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- A solution method for a car fleet management problem with maintenance constraints
- Clique tree generalization and new subclasses of chordal graphs
- Dot product representations of graphs
- A note on superbrittle graphs
- On the structure of graphs with few \(P_4\)s
- Hamiltonian circuits in interval graph generalizations
- Enumeration of difference graphs
- Powers of distance-hereditary graphs
- Weighted independent perfect domination on cocomparability graphs
- On a graph-theoretical model for cyclic register allocation
- Maximum induced matchings for chordal graphs in linear time
- An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
- On dimensional properties of graphs
- Some properties of minimal imperfect graphs
- Optimal packing and covering in the plane are NP-complete
- Block duplicate graphs and a hierarchy of chordal graphs
- Online independent sets.
- Algorithms for weakly triangulated graphs
- Toughness, hamiltonicity and split graphs
- The conditional covering problem on unweighted interval graphs with nonuniform coverage radius
- On the approximability of an interval scheduling problem
- A lower bound for the job insertion problem.
- Algorithms for solving problems on graphs of bounded pathwidth
- New results on induced matchings
- The Hamiltonian problem on distance-hereditary graphs
- New sufficient conditions for \(\alpha\)-redundant vertices
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)
