Trapezoid graphs and their coloring
From MaRDI portal
Publication:1111577
DOI10.1016/0166-218X(88)90032-7zbMath0658.05067MaRDI QIDQ1111577
Ron Yair Pinter, Ido Dagan, Martin Charles Golumbic
Publication date: 1988
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
trapezoid graphsinterval graphspermutation graphsincomparability graphschannel routingcoloring algorithm
Related Items
A parallel algorithm for solving the coloring problem on trapezoid graphs, A linear time algorithm for finding depth-first spanning trees on trapezoid graphs, On the computational complexity of 2-interval pattern matching problems, Dominations in trapezoid graphs, A recognition algorithm for orders of interval dimension two, Computing a dominating pair in an asteroidal triple-free graph in linear time, Parallel algorithms for the domination problems in trapezoid graphs, On powers of \(m\)-trapezoid graphs, Measuring the vulnerability for classes of intersection graphs, Tangent circle graphs and `orders', On the structure of trapezoid graphs, On Strict (Outer-)Confluent Graphs, Proper and unit bitolerance orders and graphs, Efficient algorithms for the minimum connected domination on trapezoid graphs, Max-min weight balanced connected partition, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, A recognition algorithm for simple-triangle graphs, Efficient algorithm for the vertex connectivity of trapezoid graphs, Triangulating multitolerance graphs, An efficient algorithm to solve the conditional covering problem on trapezoid graphs, Asteroidal triple-free graphs, On linear and circular structure of (claw, net)-free graphs, Donation center location problem, The recognition of triangle graphs, Computation of inverse 1-center location problem on the weighted trapezoid graphs, Connected domination and dominating clique in trapezoid graphs, Approximation of RNA multiple structural alignment, Approximating the 2-interval pattern problem, A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph, Extracting constrained 2-interval subsets in 2-interval sets, New results on induced matchings, Solving the single step graph searching problem by solving the maximum two-independent set problem, A linear time algorithm to compute a dominating path in an AT-free graph, How to use the minimal separators of a graph for its chordal triangulation, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, Trapezoid graphs and generalizations, geometry and algorithms, Unit and proper tube orders, A linear time algorithm to construct a tree 4-spanner on trapezoid graphs, Optimal grid representations, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, Dimension-2 poset competition numbers and dimension-2 poset double competition numbers, Trapezoid graphs and generalizations, geometry and algorithms, Counting maximal independent sets in directed path graphs, A characterization of interval orders with semiorder dimension two, Counting the number of vertex covers in a trapezoid graph, The hub number of co-comparability graphs, Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs, The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial, Efficient maximum matching algorithms for trapezoid graphs, Distributed interactive proofs for the recognition of some geometric intersection graph classes, Interval dimension is a comparability invariant, An efficient algorithm to generate all maximal independent sets on trapezoid graphs, Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs, An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs, AN IMPROVED PARALLEL ALGORITHM FOR A GEOMETRIC MATCHING PROBLEM WITH APPLICATION TO TRAPEZOID GRAPHS
Cites Work
- Tolerance graphs
- Comparability graphs and intersection graphs
- Betweenness, orders and interval graphs
- Optimal Placement for River Routing
- The Complexity of the Partial Order Dimension Problem
- The NP-completeness column: an ongoing guide
- Permutation Graphs and Transitive Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
