Algorithmic graph theory and perfect graphs
From MaRDI portal
Publication:1886097
zbMath1050.05002MaRDI QIDQ1886097
Publication date: 15 November 2004
Published in: Annals of Discrete Mathematics (Search for Journal in Brave)
split graphintersection graphcomparability graphperfect graphchordal graphinterval graphefficient algorithmthreshold graphcircle graphpermutation graphchordal bipartite graphtriangulated graph
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Perfect graphs (05C17) Algorithms in computer science (68W99)
Related Items
Balanced independent and dominating sets on colored interval graphs, On minimum generalized Manhattan connections, Cyclability in graph classes, On the \(m\)-clique free interval subgraphs polytope: polyhedral analysis and applications, NP-hardness of the recognition of coordinated graphs, On the complexity of cover-incomparability graphs of posets, Deleting edges to restrict the size of an epidemic: a new application for treewidth, The skiving stock problem and its relation to hypergraph matchings, Triangulated neighborhoods in even-hole-free graphs, Secure domination in proper interval graphs, Homothetic polygons and beyond: maximal cliques in intersection graphs, Enumeration and maximum number of minimal connected vertex covers in graphs, The \(k\)-hop connected dominating set problem: approximation and hardness, 3-colouring AT-free graphs in polynomial time, \(L(0,1)\)-labelling of permutation graphs, Combinatorial problems on \(H\)-graphs, Two-layer drawings of bipartite graphs, Graph limits and hereditary properties, New characterizations of proper interval bigraphs, Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs, On the intersection of tolerance and cocomparability graphs, A tie-break model for graph search, The longest path problem is polynomial on cocomparability graphs, Finding cliques of maximum weight on a generalization of permutation graphs, Stratified graphical models -- context-specific independence in graphical models, The firefighter problem on graph classes, Critical exponents of graphs, Thinning out Steiner trees: a node-based model for uniform edge costs, On orthogonal ray trees, Integral mixed unit interval graphs, Normal Helly circular-arc graphs and its subclasses, A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs, Interval graph limits, Degenerate matchings and edge colorings, A unified matheuristic for solving multi-constrained traveling salesman problems with profits, Graphs vertex-partitionable into strong cliques, Associated primes of powers of edge ideals, Fully dynamic representations of interval graphs, A fully dynamic graph algorithm for recognizing interval graphs, A bottleneck detection algorithm for complex product assembly line based on maximum operation capacity, Coloring square-free Berge graphs, Fair cost allocations under conflicts - a game-theoretic point of view -, Unoriented Laplacian maximizing graphs are degree maximal, On spectrum assignment in elastic optical tree-networks, Counting the number of independent sets in chordal graphs, Tractabilities and intractabilities on geometric intersection graphs, Vulnerability of subclasses of chordal graphs, Circle graphs and monadic second-order logic, The critical exponent: a novel graph invariant, Maximum induced matching algorithms via vertex ordering characterizations, On the complexity of computing treebreadth, The critical node detection problem in networks: a survey, Aliased register allocation for straight-line programs is NP-complete, Polyhedral studies of vertex coloring problems: the standard formulation, The Hamiltonian connectivity of rectangular supergrid graphs, The 0-1 inverse maximum stable set problem, On compatibility and incompatibility of collections of unrooted phylogenetic trees, Models and algorithms for reliability-oriented dial-a-ride with autonomous electric vehicles, Saving colors and max coloring: some fixed-parameter tractability results, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, Minimal proper interval completions, Approximation algorithm for coloring of dotted interval graphs, On minimal vertex separators of dually chordal graphs: properties and characterizations, On \(L(2,1)\)-coloring split, chordal bipartite, and weakly chordal graphs, On right-angled Artin groups without surface subgroups., New algorithms and complexity status of the reducibility problem of sequences in open shop scheduling minimizing the makespan, Minimal split completions, On the approximate compressibility of connected vertex cover, The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness, Obstacle numbers of graphs, \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs, Multivariate time series analysis from a Bayesian machine learning perspective, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, A simple algorithm to find Hamiltonian cycles in proper interval graphs, Dyadic representations of graphs, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Spectral characterizations of anti-regular graphs, Maximum rooted connected expansion, The \(\langle t \rangle \)-property of some classes of graphs, Recognizing edge clique graphs among interval graphs and probe interval graphs, Binomial edge ideals of regularity 3, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, Equivalences and the complete hierarchy of intersection graphs of paths in a tree, Routing to reduce the cost of wavelength conversion, A vertex ordering characterization of simple-triangle graphs, Efficient algorithms for network localization using cores of underlying graphs, Partial characterizations of coordinated graphs: Line graphs and complements of forests, Minimum entropy coloring, Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs, Intersection models of weakly chordal graphs, Dynamically maintaining split graphs, Labeling bipartite permutation graphs with a condition at distance two, The clique-separator graph for chordal graphs, Laminar structure of ptolemaic graphs with applications, Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time, Containment relations in split graphs, An output sensitive algorithm for computing a maximum independent set of a circle graph, Perfectness and imperfectness of unit disk graphs on triangular lattice points, On b-perfect chordal graphs, Characterizations and recognition of circular-arc graphs and subclasses: a survey, Partial Lasserre relaxation for sparse Max-Cut, Transversals of longest cycles in partial k‐trees and chordal graphs, Independent set under a change constraint from an initial solution, Enumeration of minimal tropical connected sets, Broadcasting in split graphs, Partitioning subclasses of chordal graphs with few deletions, Multithreshold multipartite graphs, The firebreak problem, Toughness and Hamiltonicity of strictly chordal graphs, Graphon convergence of random cographs, Colouring a dominating set without conflicts: \(q\)-subset square colouring, A story of diameter, radius, and (almost) Helly property, Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs, Certifying induced subgraphs in large graphs, Assistance and interdiction problems on interval graphs, Complement of the Generalized Total Graph of Commutative Rings – A Survey, Comparability graphs among cover-incomparability graphs, \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs, Representing formulas of propositional logic by cographs, permutations and tables, Partitioning subclasses of chordal graphs with few deletions, A shift-based model to solve the integrated staff rostering and task assignment problem with real-world requirements, Star covers and star partitions of double-split graphs, Partial and simultaneous transitive orientations via modular decompositions, Graph Bipartization Problem with Applications to Via Minimization in VLSI Design, Deletion to scattered graph classes. I: Case of finite number of graph classes, Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded, Treewidth versus clique number. II: Tree-independence number, Supersolvable saturated matroids and chordal graphs, Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes, On characterizing proper max-point-tolerance graphs, Correcting the algorithm for a minimum secure dominating set of proper interval graphs by Zou, Liu, Hsu and Wang, Chain graph sequences and Laplacian spectra of chain graphs, Graphs of fixed order and size with maximal \(A_\alpha\)-index, Path eccentricity of graphs, On minimally non-firm binary matrices, REGULAR EXTENSION OF GRAPHS, Complexity of maximum cut on interval graphs, Independence polynomials and hypergeometric series, Scheduling appointments online: the power of deferred decision-making, Succinct data structure for path graphs, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, A characterization of unit interval bigraphs of open and closed intervals, Directed path graph isomorphism, Strictly chordal graphs: structural properties and integer Laplacian eigenvalues, Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\), On the hardness of inclusion-wise minimal separators enumeration, First-order logic axiomatization of metric graph theory, Solving the routing and spectrum assignment problem, driven by combinatorial properties, Online coloring of short intervals, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Recognizing Proper Tree-Graphs, Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, On the Parameterized Approximability of Contraction to Classes of Chordal Graphs, A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs, Clique-width of path powers, Algorithms for finding disjoint path covers in unit interval graphs, Enumerating minimal connected dominating sets in graphs of bounded chordality, An approximate algorithm for the chromatic number of graphs, Computing role assignments of split graphs, On basic chordal graphs and some of its subclasses, On the OBDD representation of some graph classes, A linear time algorithm to compute square of interval graphs and their colouring, Recognizability equals definability for graphs of bounded treewidth and bounded chordality, Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I, Strictly interval graphs: characterization and linear time recognition, Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs, Context-specific independence in graphical log-linear models, Hamiltonian cycles in linear-convex supergrid graphs, The VC-dimension of graphs with respect to \(k\)-connected subgraphs, The load-balanced multi-dimensional bin-packing problem, Refined algorithms for hitting many intervals, Max point-tolerance graphs, A new LBFS-based algorithm for cocomparability graph recognition, Minimal dominating sets in interval graphs and trees, Local properties of simplicial complexes, Resource allocation with time intervals, On the parameterized complexity of some optimization problems related to multiple-interval graphs, Roman domination on strongly chordal graphs, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Algorithms for interval structures with applications, Matrices attaining the minimum semidefinite rank of a chordal graph, An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem, Parameterized complexity of vertex deletion into perfect graph classes, Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization, The cluster deletion problem for cographs, A Dirac-type characterization of \(k\)-chordal graphs, Theorems on partitioned matrices revisited and their applications to graph spectra, Graph classes and Ramsey numbers, Finding clubs in graph classes, The price of connectivity for dominating set: upper bounds and complexity, Finding intersection models: from chordal to Helly circular-arc graphs, On the spectrum of threshold graphs, Reduced clique graphs of chordal graphs, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, Random generation and enumeration of bipartite permutation graphs, Retaining positive definiteness in thresholded matrices, A characterization of graphs with rank 5, Edge search number of cographs, An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs, Linear-time recognition of Helly circular-arc models and graphs, A note on chromatic properties of threshold graphs, Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs, Characterization and representation problems for intersection betweennesses, Edge contractions in subclasses of chordal graphs, On the online track assignment problem, Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs, The longest path problem has a polynomial solution on interval 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, Partial characterizations of circle graphs, Acyclic and star colorings of cographs, Computing role assignments of proper interval graphs in polynomial time, A characterization of chain probe graphs, A min-flow algorithm for minimal critical set detection in resource constrained project scheduling, Strongly chordal and chordal bipartite graphs are sandwich monotone, Vertex-transitive CIS graphs, Practical and efficient circle graph recognition, Practical and efficient split decomposition via graph-labelled trees, A simple linear-time recognition algorithm for weakly quasi-threshold graphs, Dirac's theorem on simplicial matroids, Induced subgraph isomorphism on proper interval and bipartite permutation graphs, On the number of minimal dominating sets on some graph classes, Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs, Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs, Approximation algorithms for maximum independent set of a unit disk graph, The circumference of the square of a connected graph, Interval graph representation with given interval and intersection lengths, Finding disjoint paths in split graphs, On a class of graphs between threshold and total domishold graphs, Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs, The Hamiltonian properties of supergrid graphs, New results on Ptolemaic graphs, \(L(2,1)\)-labeling of interval graphs, Complexity of simplicial homology and independence complexes of chordal graphs, A linear-time algorithm for clique-coloring problem in circular-arc graphs, Extending partial representations of proper and unit interval graphs, On counting interval lengths of interval graphs, Transitive orientations in bull-reducible Berge graphs, On graphs without a \(C_{4}\) or a diamond, Separator orders in interval, cocomparability, and AT-free graphs, On the page number of RNA secondary structures with pseudoknots, Coloring translates and homothets of a convex body, Enumeration of the perfect sequences of a chordal graph, Treewidth and minimum fill-in on permutation graphs in linear time, Some notes on the threshold graphs, Mixed unit interval graphs, An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs, On the complete width and edge clique cover problems, The induced separation dimension of a graph, Approximability of clique transversal in perfect graphs, Enumerating minimal dominating sets in chordal graphs, Subgraph extraction and metaheuristics for the maximum clique problem, Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs, Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph, Recognizing graph search trees, An extended depth-first search algorithm for optimal triangulation of Bayesian networks, On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs, The scattering number of strictly chordal graphs: linear time determination, Well-partitioned chordal graphs, Linear structure of bipartite permutation graphs and the longest path problem, Subtree filament graphs are subtree overlap graphs, Embedding ray intersection graphs and global curve simplification, 2-nested matrices: towards understanding the structure of circle graphs, Isomorphism testing for \(T\)-graphs in FPT, Online scheduling of car-sharing request pairs between two locations, Combinatorics, graph theory, and computing, Tree search for the stacking problem, Structural parameterizations with modulator oblivion, On the rank of the distance matrix of graphs, Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy, A simple linear time algorithm to solve the MIST problem on interval graphs, Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees, Good characterizations and linear time recognition for 2-probe block graphs, Enumeration of minimal connected dominating sets for chordal graphs, Minimal asymmetric graphs, Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity, Extending partial representations of interval graphs, Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}, Building efficient and compact data structures for simplicial complexes, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, Subgraph complementation, An algorithmic characterization of splitting signed graph, Parameterized aspects of strong subgraph closure, On the chromatic number of (\(P_6\), diamond)-free graphs, On polygon numbers of circle graphs and distance hereditary graphs, Complexity-separating graph classes for vertex, edge and total colouring, Characterizing interval graphs which are probe unit interval graphs, A recognition algorithm for simple-triangle graphs, Marginal and simultaneous predictive classification using stratified graphical models, Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS, A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs, Bounds on regularity of quadratic monomial ideals, On the tractability of optimization problems on \(H\)-graphs, A dichotomy for minimum cost graph homomorphisms, On strict (outer-)confluent graphs, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, On the domination number of permutation graphs and an application to strong fixed points, Robust maximum weighted independent-set problems on interval graphs, Computation of inverse 1-center location problem on the weighted trapezoid graphs, Intersection dimension and graph invariants, The longest cycle problem is polynomial on interval graphs, Integer Laplacian eigenvalues of chordal graphs, Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes, Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs, A certifying and dynamic algorithm for the recognition of proper circular-arc graphs, Algorithms for generating strongly chordal graphs, Latent association graph inference for binary transaction data, Scheduling jobs with normally distributed processing times on parallel machines, Detecting fixed patterns in chordal graphs in polynomial time, An intersection model for multitolerance graphs: efficient algorithms and hierarchy, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, Laplacian controllability classes for threshold graphs, Graphs with maximal signless Laplacian spectral radius, Vertex splitting and the recognition of trapezoid graphs, The complexity of the defensive domination problem in special graph classes, Generalised online colouring problems in overlap graphs, Representing graphs as the intersection of cographs and threshold graphs, The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw, Profit maximization in flex-grid all-optical networks, On the threshold of intractability, On superperfection of edge intersection graphs of paths, The complexity of the vertex-minor problem, Representing point sets on the plane as permutations, Avoidable vertices and edges in graphs: existence, characterization, and applications, Enumeration and maximum number of minimal dominating sets for chordal graphs, Revisiting connected vertex cover: FPT algorithms and lossy kernels, Colouring square-free graphs without long induced paths, Succinct navigational oracles for families of intersection graphs on a circle, Block-indifference graphs: characterization, structural and spectral properties, Probabilistic pursuits on graphs, A type of algebraic structure related to sets of intervals, Forbidden induced subgraph characterization of circle graphs within split graphs, On subclasses of interval count two and on Fishburn's conjecture, Connected matchings in chordal bipartite graphs, Coloring a dominating set without conflicts: \(q\)-subset square coloring, Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity, Distributed interactive proofs for the recognition of some geometric intersection graph classes, Clique-width of full bubble model graphs, Obtaining matrices with the consecutive ones property by row deletions, Online results for black and white bin packing, A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs, Extending partial representations of subclasses of chordal graphs, Normality criteria for monomial ideals, The eternal dominating set problem for proper interval graphs, Linear-time algorithms for tree root problems, On maximum independent set of categorical product and ultimate categorical ratios of graphs, Fast distance multiplication of unit-Monge matrices, Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs, On the interval chromatic number of proper interval graphs, Fragmented coloring of proper interval and split graphs, Graphs and digraphs represented by intervals and circular arcs, Graphical group ridge, Improved bounds for colouring circle graphs, Assessing the Computational Complexity of Multi-layer Subgraph Detection, Linear-Time Generation of Random Chordal Graphs, Finding a Perfect Phylogeny from Mixed Tumor Samples, Fair Packing of Independent Sets, A Survey on Spanning Tree Congestion, Lifting for Simplicity: Concise Descriptions of Convex Sets, Letter Graphs and Geometric Grid Classes of Permutations, Labelled well-quasi-order for permutation classes, Additive Spanners for Circle Graphs and Polygonal Graphs, Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs, From a Circular-Arc Model to a Proper Circular-Arc Model, An Algorithmic Characterization of sigraphs whose second iterated line sigraphs and common-edge sigraphs are switching equivalent, The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs, Edge Search Number of Cographs in Linear Time, CFI Construction and Balanced Graphs, Edge-Intersection Graphs of k-Bend Paths in Grids, Convex Recoloring Revisited: Complexity and Exact Algorithms, Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone, On some subclasses of interval catch digraphs, Picker Routing in AGV-Assisted Order Picking Systems, On Strict (Outer-)Confluent Graphs, Graph layout problems, Computing list homomorphisms in geometric intersection graphs, Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates, A Model for Birdwatching and other Chronological Sampling Activities, Linear optimization over homogeneous matrix cones, MaxCut on permutation graphs is NP‐complete, Parameterized complexity of multicut in weighted trees, Counting single-qubit Clifford equivalent graph states is #P-complete, Unnamed Item, Unnamed Item, Counting and enumerating unlabeled split–indifference graphs, Improved High Dimensional Discrete Bayesian Network Inference using Triplet Region Construction, EPG-representations with Small Grid-Size, Unnamed Item, A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs, An optimal algorithm to find minimum k-hop dominating set of interval graphs, Template-driven rainbow coloring of proper interval graphs, SURFACE SUBGROUPS OF GRAPH PRODUCTS OF GROUPS, On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs, Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs, Unit Interval Graphs of Open and Closed Intervals, Star Partitions of Perfect Graphs, Partitioning a graph into complementary subgraphs, A Bregman extension of quasi-Newton updates I: an information geometrical framework, Template-driven rainbow coloring of proper interval graphs, Unnamed Item, Intersection graphs of non-crossing paths, Unnamed Item, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, Contracting chordal graphs and bipartite graphs to paths and trees, Finding cut-vertices in the square roots of a graph, Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs, Enumeration and maximum number of maximal irredundant sets for chordal graphs, Simple Geometrical Intersection Graphs, On \(H\)-topological intersection graphs, Graph classes and the switch Markov chain for matchings, A semi-strong perfect digraph theorem, On central max-point-tolerance graphs, Some structural graph properties of the non-commuting graph of a class of finite Moufang loops, Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem, Complexity of fall coloring for restricted graph classes, Parameterized complexity of conflict-free set cover, Computing maximum independent set on outerstring graphs and their relatives, Strong cliques in diamond-free graphs, On finding separators in temporal split and permutation graphs, Context-Specific and Local Independence in Markovian Dependence Structures, Vertex deletion on split graphs: beyond 4-hitting set, Recognizing \(k\)-clique extendible orderings, Combinatorics and algorithms for quasi-chain graphs, On finding separators in temporal split and permutation graphs, Subset feedback vertex set in chordal and split graphs, The parameterized complexity of cycle packing: indifference is not an issue, On the Geometry of the Last Passage Percolation Problem, Stackelberg packing games, Contracting chordal graphs and bipartite graphs to paths and trees, Linear separation of connected dominating sets in graphs, Unnamed Item, Square-Free Graphs with No Six-Vertex Induced Path, $(2P_2,K_4)$-Free Graphs are 4-Colorable, Counting Perfect Matchings and the Switch Chain, An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs, Kernelization of Graph Hamiltonicity: Proper $H$-Graphs, The Recognition Problem of Graph Search Trees, The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial, Reconfiguration of Colorable Sets in Classes of Perfect Graphs, Efficient Local Representations of Graphs, Circle graphs are quadratically χ‐bounded, Efficient maximum matching algorithms for trapezoid graphs, Complement of the generalized total graph of fields, To reorient is easier than to orient: An on-line algorithm for reorientation of graphs, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Linear-time recognition of double-threshold graphs, Maximum Induced Matching Algorithms via Vertex Ordering Characterizations, Fast Diameter Computation within Split Graphs, Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs, Partial Characterizations of 1‐Perfectly Orientable Graphs, Working time constraints in operational fixed job scheduling, Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration, Computing the clique-separator graph for an interval graph in linear time, The \((p, q)\)-extremal problem and the fractional chromatic number of Kneser hypergraphs, On some applications of the selective graph coloring problem, Characterizing directed path graphs by forbidden asteroids, Vizing bound for the chromatic number on some graph classes, Reconfiguration of colorable sets in classes of perfect graphs, Solving the maximum internal spanning tree problem on interval graphs in polynomial time, Induced Separation Dimension, On b-vertex and b-edge critical graphs, The Longest Path Problem Is Polynomial on Interval Graphs, Path Problems in Complex Networks, On the nil-graph of ideals of commutative Artinian rings, Chordal multipartite graphs and chordal colorings, Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth, A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem, Parameterized and exact algorithms for class domination coloring, Succinct encodings for families of interval graphs, Colouring square-free graphs without long induced paths., Counting List Matrix Partitions of Graphs, Hadwiger Number of Graphs with Small Chordality, A Characterization of Mixed Unit Interval Graphs, Beyond Helly graphs: the diameter problem on absolute retracts, Minimum Average Distance Clique Trees, Complete edge-colored permutation graphs, Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number, Distance problems within Helly graphs and \(k\)-Helly graphs, Mixed Search Number of Permutation Graphs, Mixed Search Number and Linear-Width of Interval and Split Graphs, Connected graphs of fixed order and size with maximal \(A_\alpha \)-index: the one-dominating-vertex case, A Multigrid Approach to SDP Relaxations of Sparse Polynomial Optimization Problems, Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs, A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs, On the boxicity of Kneser graphs and complements of line graphs, Trajectory Control in Nonlinear Networked Systems and Its Applications to Complex Biological Systems, Enumerating Minimal Tropical Connected Sets, Demand Hitting and Covering of Intervals, Reconfiguration of cliques in a graph, Fair allocation of indivisible items with conflict graphs, Sorting under partial information (without the ellipsoid algorithm)., Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals, On dominating sets whose induced subgraphs have a bounded diameter, Computing square roots of trivially perfect and threshold graphs, On the number of non-dominated points of a multicriteria optimization problem, Subset feedback vertex sets in chordal graphs, Computing and counting longest paths on circular-arc graphs in polynomial time, Structural results on circular-arc graphs and circle graphs: a survey and the main open problems, On the correspondence between tree representations of chordal and dually chordal graphs, Co-TT graphs and a characterization of split co-TT graphs, Equistable simplicial, very well-covered, and line graphs, An efficient representation of chordal graphs, Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem, Computing Role Assignments of Proper Interval Graphs in Polynomial Time, One-phase algorithm for the determination of minimal vertex separators of chordal graphs, Algorithms for Interval Structures with Applications, NP-hard graph problems and boundary classes of graphs, Edge Contractions in Subclasses of Chordal Graphs, Unique Perfect Phylogeny Is NP-Hard, SUBEXPONENTIAL INTERVAL GRAPHS GENERATED BY IMMIGRATION–DEATH PROCESSES, The complete optimal stars-clustering-tree problem, The \(k\)-edge intersection graphs of paths in a tree, Representing edge intersection graphs of paths on degree 4 trees, Packing triangles in low degree graphs and indifference graphs, A matrix characterization of interval and proper interval graphs, On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems, Independent set of intersection graphs of convex objects in 2D, Unnamed Item, The Longest Path Problem is Polynomial on Cocomparability Graphs, From Path Graphs to Directed Path Graphs, Random Generation and Enumeration of Proper Interval Graphs, A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs, ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES, A note on adding and deleting edges in hierarchical log-linear models, Characterizing and recognizing probe block graphs, On the Power of Graph Searching for Cocomparability Graphs, Expansion and contraction functors on matriods, A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs, Optimal edge-coloring with edge rate constraints, Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, Latency Constrained Aggregation in Chain Networks Admits a PTAS, Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs, Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs, APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES, Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs, Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid, Partial characterizations of circular-arc graphs, Characterizing path graphs by forbidden induced subgraphs, Distributed Computing of Efficient Routing Schemes in Generalized Chordal Graphs, A new representation of proper interval graphs with an application to clique-width, On λ-coloring split, chordal bipartite and weakly chordal graphs, The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes, Finding a Maximum-Weight Convex Set in a Chordal Graph, Uniquely Restricted Matchings in Interval Graphs, k-separator chordal graphs: leafage and subfamilies, On balanced graphs, Read-Once Functions Revisited and the Readability Number of a Boolean Function, Profit Maximization in Flex-Grid All-Optical Networks
