Efficient graph representations
From MaRDI portal
Publication:1396949
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph representations (geometric and intersection representations, etc.) (05C62) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Perfect graphs (05C17) General topics in the theory of algorithms (68W01)
Recommendations
Cited in
(only showing first 100 items - show all)- An efficient representation of chordal graphs
- Coloring \((4K_1,C_4,C_6)\)-free graphs
- Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
- Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
- Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
- Computing a clique tree with the algorithm maximal label search
- Totally balanced dissimilarities
- Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs
- Feedback vertex set on AT-free graphs
- Sublinear approximation algorithms for boxicity and related problems
- A compact encoding of unordered binary trees
- On orthogonal ray trees
- On word-representable and multi-word-representable graphs
- Laminar structure of ptolemaic graphs with applications
- Recognizing graphs without asteroidal triples
- Linear structure of bipartite permutation graphs and the longest path problem
- On list \(k\)-coloring convex bipartite graphs
- Algorithmic aspects of intersection graphs and representation hypergraphs
- A new representation of proper interval graphs with an application to clique-width
- Compact representation of graphs with bounded bandwidth or treedepth
- Homothetic polygons and beyond: maximal cliques in intersection graphs
- scientific article; zbMATH DE number 2230210 (Why is no real title available?)
- The number of disk graphs
- Games on interval and permutation graph representations
- Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
- Extending partial representations of subclasses of chordal graphs
- Structure and algorithms for (cap, even hole)-free graphs
- Simultaneous representation of proper and unit interval graphs
- Complexity of Hamiltonian cycle reconfiguration
- Efficient Low-Level Connection Tableaux
- Compact representation of graphs of small clique-width
- The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
- On forbidden induced subgraphs for unit disk graphs
- An implicit representation of chordal comparability graphs in linear time
- Fully dynamic representations of interval graphs
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- Triangulated neighborhoods in even-hole-free 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
- On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
- On 2-Subcolourings of Chordal Graphs
- Totally Balanced Formal Context Representation
- Implicit representation conjecture for semi-algebraic graphs
- Parameterized complexity of induced graph matching on claw-free graphs
- A distance measure for large graphs based on prime graphs
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Transitive orientations in bull-reducible Berge graphs
- Strict chordal digraphs viewed as graphs with distinguished edges
- Efficient data structures for sparse network representation
- Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
- Algorithms for induced biclique optimization problems
- Complete branching rules for Specht modules
- Complexity-separating graph classes for vertex, edge and total colouring
- A vertex ordering characterization of simple-triangle graphs
- Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes
- A note on completing quasi-distance and distance matrices
- Reconfiguration of Colorable Sets in Classes of Perfect Graphs
- New geometric representations and domination problems on tolerance and multitolerance graphs
- Representations of graphs and networks (coding, packings and embeddings)
- Structural parameterizations with modulator oblivion
- Inductive computations on graphs defined by clique-width expressions
- Recognizing threshold tolerance graphs in \(O(n^2)\) time
- Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
- Chromatic polynomials of oriented graphs
- Minimum cost flow problem with conflicts
- Structural parameterizations with modulator oblivion
- Binary set systems and totally balanced hypergraphs
- Containment graphs and posets of paths in a tree: wheels and partial wheels
- Average case analysis for tree labelling schemes
- Graph parameters, implicit representations and factorial properties
- Graph classes and the switch Markov chain for matchings
- Exact algorithms for weak Roman domination
- A type of algebraic structure related to sets of intervals
- Helly EPT graphs on bounded degree trees: characterization and recognition
- Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
- Graph parameters, implicit representations and factorial properties
- Efficientk-NN graph construction for graphs on variables
- Optimal adjacency labels for subgraphs of Cartesian products
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
- Graph functionality
- Treewidth versus clique number. II: Tree-independence number
- Fair allocation of indivisible items with conflict graphs
- On the speed of algebraically defined graph classes
- The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
- New tools to study 1-11-representation of graphs
- Succinct navigational oracles for families of intersection graphs on a circle
- A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
- Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation
- Linear algorithms for chordal graphs of bounded directed vertex leafage
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
- Logical labeling schemes
- An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
- Optimal data reduction for graph coloring using low-degree polynomials
- Constrained representations of map graphs and half-squares
- Fair allocation algorithms for indivisible items under structured conflict constraints
- Reconfiguration of colorable sets in classes of perfect graphs
This page was built for publication: Efficient graph representations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1396949)
