Efficient graph representations

zbMath1033.05001MaRDI QIDQ1396949

Jeremy P. Spinrad

Publication date: 15 July 2003

Published in: Fields Institute Monographs (Search for Journal in Brave)

zbMATH Keywords

algorithmimplicit representationgraph class

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph representations (geometric and intersection representations, etc.) (05C62) Perfect graphs (05C17) General topics in the theory of algorithms (68W01)

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

Structural parameterizations for boxicity ⋮ A unified approach to recognize squares of split graphs ⋮ On the OBDD representation of some graph classes ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ On containment graphs of paths in a tree ⋮ Efficient and perfect domination on circular-arc graphs ⋮ A note on path domination ⋮ Ferrers dimension of grid intersection graphs ⋮ A new LBFS-based algorithm for cocomparability graph recognition ⋮ On recognition of threshold tolerance graphs and their complements ⋮ Characterization and recognition of some opposition and coalition graph classes ⋮ The minimum vulnerability problem on specific graph classes ⋮ Structural parameterizations with modulator oblivion ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Computing a clique tree with the algorithm maximal label search ⋮ Triangulated neighborhoods in even-hole-free graphs ⋮ Graph parameters, implicit representations and factorial properties ⋮ An adjacency labeling scheme based on a decomposition of trees into caterpillars ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Strict chordal digraphs viewed as graphs with distinguished edges ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ Recognizing graphs without asteroidal triples ⋮ Satisfiability of acyclic and almost acyclic CNF formulas ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ A recognition algorithm for simple-triangle graphs ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Permutation bigraphs and interval containments ⋮ Complete branching rules for Specht modules ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ On the intersection of tolerance and cocomparability graphs ⋮ Sphere and dot product representations of graphs ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ Games on interval and permutation graph representations ⋮ Random generation and enumeration of bipartite permutation graphs ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Linear-time recognition of Helly circular-arc models and graphs ⋮ Arboricity, \(h\)-index, and dynamic algorithms ⋮ A good characterization of squares of strongly chordal split graphs ⋮ Algorithms for induced biclique optimization problems ⋮ On orthogonal ray trees ⋮ The recognition of triangle graphs ⋮ Enumeration of \((0.1)\)-matrices avoiding some \(2 \times 2\) matrices ⋮ Fully dynamic representations of interval graphs ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ Subgraph isomorphism in graph classes ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Decomposition by maxclique separators ⋮ Enumerating minimal subset feedback vertex sets ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Implicit representations and factorial properties of graphs ⋮ Dominating induced matchings for \(P_7\)-free graphs in linear time ⋮ Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs ⋮ On the speed of algebraically defined graph classes ⋮ Counting the number of independent sets in chordal graphs ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Implicit representation conjecture for semi-algebraic graphs ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Polygon-circle and word-representable graphs ⋮ The Dilworth number of auto-chordal bipartite graphs ⋮ On the recognition of unit disk graphs and the distance geometry problem with ranges ⋮ Feedback vertex set on AT-free graphs ⋮ Circle graphs and monadic second-order logic ⋮ Recent results on containment graphs of paths in a tree ⋮ A distance measure for large graphs based on prime graphs ⋮ Transitive orientations in bull-reducible Berge graphs ⋮ On graphs without a \(C_{4}\) or a diamond ⋮ Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ The square of a block graph ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Characterising \((k,\ell )\)-leaf powers ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs ⋮ An implicit representation of chordal comparability graphs in linear time ⋮ Enumeration of the perfect sequences of a chordal graph ⋮ Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ The clique operator on circular-arc graphs ⋮ Compact representation of graphs of small clique-width ⋮ An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs ⋮ On forbidden induced subgraphs for unit disk graphs ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Equivalences and the complete hierarchy of intersection graphs of paths in a tree ⋮ A vertex ordering characterization of simple-triangle graphs ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ Intersection models of weakly chordal graphs ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Laminar structure of ptolemaic graphs with applications ⋮ Totally balanced dissimilarities ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ A counter-example to the probabilistic universal graph conjecture via randomized communication complexity ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ A type of algebraic structure related to sets of intervals ⋮ Revising Johnson's table for the 21st century ⋮ On the isomorphism problem for Helly circular-arc graphs ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

This page was built for publication: Efficient graph representations