Efficient graph representations
From MaRDI portal
Publication:1396949
zbMath1033.05001MaRDI QIDQ1396949
Publication date: 15 July 2003
Published in: Fields Institute Monographs (Search for Journal in Brave)
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)
Average case analysis for tree labelling schemes ⋮ Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs ⋮ On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ Complexity of Hamiltonian cycle reconfiguration ⋮ Linear structure of bipartite permutation graphs and the longest path problem ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Inductive computations on graphs defined by clique-width expressions ⋮ Helly EPT graphs on bounded degree trees: characterization and recognition ⋮ Binary set systems and totally balanced hypergraphs ⋮ Containment graphs and posets of paths in a tree: wheels and partial wheels ⋮ Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time ⋮ Exact algorithms for weak Roman domination ⋮ Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ MaxCut on permutation graphs is NP‐complete ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Minimum cost flow problem with conflicts ⋮ On word-representable and multi-word-representable graphs ⋮ Linear-Interval Dimension and PI Orders ⋮ On cliques of Helly Circular-arc Graphs ⋮ Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs ⋮ Coloring \((4K_1,C_4,C_6)\)-free graphs ⋮ Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number ⋮ Circle graph isomorphism in almost linear time ⋮ Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete ⋮ Proper Helly Circular-Arc Graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ Logical labeling schemes ⋮ A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs ⋮ Unnamed Item ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ Unnamed Item ⋮ Reconfiguration of cliques in a graph ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Unnamed Item ⋮ On opposition graphs, coalition graphs, and bipartite permutation graphs ⋮ Min-Orderable Digraphs ⋮ Subset feedback vertex sets in chordal graphs ⋮ An efficient representation of chordal graphs ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs ⋮ A Compact Encoding of Unordered Binary Trees ⋮ The \(k\)-edge intersection graphs of paths in a tree ⋮ Representing edge intersection graphs of paths on degree 4 trees ⋮ Unnamed Item ⋮ The monadic second-order logic of graphs. XV: On a conjecture by D. Seese ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Graph parameters, implicit representations and factorial properties ⋮ Algorithms for clique-independent sets on subclasses of circular-arc graphs ⋮ Vertex splitting and the recognition of trapezoid graphs ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Unnamed Item ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs ⋮ Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs ⋮ The number of disk graphs ⋮ Fully dynamic algorithm for recognition and modular decomposition of permutation graphs ⋮ Simple Geometrical Intersection Graphs ⋮ Graph classes and the switch Markov chain for matchings ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time ⋮ On 2-Subcolourings of Chordal Graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Graph functionality ⋮ Recognizing \(k\)-clique extendible orderings ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ A note on completing quasi-distance and distance matrices ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs ⋮ Unnamed Item ⋮ A new representation of proper interval graphs with an application to clique-width ⋮ Linear Algorithms for Chordal Graphs of Bounded Directed Vertex Leafage ⋮ Short Models for Unit Interval Graphs ⋮ Chromatic polynomials of oriented graphs ⋮ The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial ⋮ Shorter Labeling Schemes for Planar Graphs ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs ⋮ Totally Balanced Formal Context Representation ⋮ Extending partial representations of subclasses of chordal graphs ⋮ Colouring Some Classes of Perfect Graphs Robustly ⋮ What Graphs are 2-Dot Product Graphs? ⋮ 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
This page was built for publication: Efficient graph representations
