Algorithmic graph theory and perfect graphs
From MaRDI portal
Publication:1886097
zbMATH Open1050.05002MaRDI QIDQ1886097FDOQ1886097
Authors: Martin Charles Golumbic 
Publication date: 15 November 2004
Published in: Annals of Discrete Mathematics (Search for Journal in Brave)
Recommendations
split graphintersection graphperfect graphthreshold graphefficient algorithminterval graphchordal graphcircle graphpermutation graphcomparability graphchordal bipartite graphtriangulated graph
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Perfect graphs (05C17) Algorithms in computer science (68W99)
Cited In (only showing first 100 items - show all)
- Aliased register allocation for straight-line programs is NP-complete
- Balanced independent and dominating sets on colored interval graphs
- On minimum generalized Manhattan connections
- Linear structure of bipartite permutation graphs and the longest path problem
- Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs
- Linear-time algorithms for tree root problems
- On some subclasses of interval catch digraphs
- NP-hardness of the recognition of coordinated graphs
- APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES
- Partial characterizations of coordinated graphs: Line graphs and complements of forests
- Minimum entropy coloring
- Triangulated neighborhoods in even-hole-free graphs
- \((2P_2,K_4)\)-free graphs are 4-colorable
- An optimal algorithm to find minimum k-hop dominating set of interval graphs
- An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
- The induced separation dimension of a graph
- Approximability of clique transversal in perfect graphs
- The recognition problem of graph search trees
- On the complexity of computing treebreadth
- Random Generation and Enumeration of Proper Interval Graphs
- An efficient representation of chordal graphs
- A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
- Colouring square-free graphs without long induced paths
- Graph limits and hereditary properties
- Vizing bound for the chromatic number on some graph classes
- Efficient algorithms for network localization using cores of underlying graphs
- \(L(0,1)\)-labelling of permutation graphs
- New characterizations of proper interval bigraphs
- A tie-break model for graph search
- Critical exponents of graphs
- The firefighter problem on graph classes
- Assistance and interdiction problems on interval graphs
- An output sensitive algorithm for computing a maximum independent set of a circle graph
- The longest path problem is polynomial on cocomparability graphs
- The longest path problem has a polynomial solution on interval graphs
- On orthogonal ray trees
- Graphs vertex-partitionable into strong cliques
- Subtree filament graphs are subtree overlap graphs
- A polynomial time algorithm for longest paths in biconvex graphs
- Characterizing and recognizing probe block graphs
- A characterization of chain probe graphs
- Finding cut-vertices in the square roots of a graph
- Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
- Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs
- Edge-Intersection Graphs of k-Bend Paths in Grids
- Linear-time generation of random chordal graphs
- Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem
- A simple linear-time recognition algorithm for weakly quasi-threshold graphs
- Dirac's theorem on simplicial matroids
- On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
- On the domination number of permutation graphs and an application to strong fixed points
- Complexity of simplicial homology and independence complexes of chordal graphs
- Computing maximum independent set on outerstring graphs and their relatives
- Comparability graphs among cover-incomparability graphs
- Coloring square-free Berge graphs
- Transitive orientations in bull-reducible Berge graphs
- Separator orders in interval, cocomparability, and AT-free graphs
- On \(L(2,1)\)-coloring split, chordal bipartite, and weakly chordal graphs
- \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
- A new representation of proper interval graphs with an application to clique-width
- A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
- Partial characterizations of 1-perfectly orientable graphs
- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
- The \(\langle t \rangle \)-property of some classes of graphs
- Edge contractions in subclasses of chordal graphs
- On the online track assignment problem
- On b-perfect chordal graphs
- On counting interval lengths of interval graphs
- Simultaneous representation of proper and unit interval graphs
- Containment relations in split graphs
- Additive Spanners for Circle Graphs and Polygonal Graphs
- On right-angled Artin groups without surface subgroups.
- Distributed computing of efficient routing schemes in generalized chordal graphs
- Distributed computing of efficient routing schemes in generalized chordal graphs
- Ordered coloring of grids and related graphs
- Collective additive tree spanners for circle graphs and polygonal graphs
- Restricted vertex multicut on permutation graphs
- Labelled well-quasi-order for permutation classes
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- Extending partial representations of subclasses of chordal graphs
- Intersection dimension and graph invariants
- A min-flow algorithm for minimal critical set detection in resource constrained project scheduling
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Practical and efficient split decomposition via graph-labelled trees
- Dynamically maintaining split graphs
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
- Counting the number of independent sets in chordal graphs
- Graph layout problems
- Induced subgraph isomorphism on proper interval and bipartite permutation graphs
- Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
- An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs
- Characterization and representation problems for intersection betweennesses
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- Approximation algorithms for maximum independent set of a unit disk graph
- A fully dynamic graph algorithm for recognizing interval graphs
- Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
- Finding disjoint paths in split graphs
- On a class of graphs between threshold and total domishold graphs
- On the page number of RNA secondary structures with pseudoknots
This page was built for publication: Algorithmic graph theory and perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1886097)
