Works (58)
Updated: September 23rd, 2024 08:17
2022 article
Faster Decomposition ofWeighted Graphs into Cliques using Fisher's Inequality
ArXiv.
Source: ORCID
Added: August 6, 2022
2022 article
UN Sustainable Development Goal Categories
16. Peace, Justice and Strong Institutions
(OpenAlex)
Source: ORCID
Added: August 6, 2022
2022 article
Source: ORCID
Added: August 6, 2022
2021 journal article
An Updated Experimental Evaluation of Graph Bipartization Methods
ACM Journal of Experimental Algorithmics, 26.
Contributors: T. Goodrich n, E. Horton n & n
TL;DR:
It is found that for heuristic solutions with time constraints under a second, iterative compression routines jump-started with a heuristic solution perform best, after which point using a highly tuned solver like CPLEX is worthwhile.
(via Semantic Scholar)
open access via arxiv.org (repository)
Source: ORCID
Added: August 6, 2022
2021 article
Hardness of the Generalized Coloring Numbers
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85121786987&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2021 journal article
On the threshold of intractability
Journal of Computer and System Sciences, 124, 1–25.
Contributors: P. Drange *, M. Dregi*, D. Lokshtanov * & *
author keywords: Edge editing; Threshold graphs; Parameterized complexity
Source: ORCID
Added: August 6, 2022
2021 conference paper
Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition
SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), 111–122.
TL;DR:
A new combinatorial model for identifying regulatory modules in gene co-expression data using a decomposition into weighted cliques is presented, and two new algorithms for finding these decompositions are presented, using linear programming and integer partitioning to determine the clique weights.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2021 article
Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85108789587&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2021 article
Projecting genetic associations through gene expression patterns highlights disease etiology and drug mechanisms
BioRxiv.
Contributors: M. Pividori *, S. Lu *, B. Li *, C. Su *, M. Johnson *, W. Wei *, Q. Feng *, B. Namjou *
TL;DR:
PhenoPLIER is introduced, a computational approach that maps gene-trait associations and pharmacological perturbation data into a common latent representation for a joint analysis that is accurate in predicting known drug-disease pairs and inferring mechanisms of action.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2021 article
Sparse dominating sets and balanced neighborhood partitioning
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85121833484&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2020 article
A color-avoiding approach to subgraph counting in bounded expansion classes
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85095561220&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2020 journal article
Exploring neighborhoods in large metagenome assembly graphs using spacegraphcats reveals hidden sequence diversity
GENOME BIOLOGY, 21(1).
Contributors: C. Brown *, D. Moritz *, . M.P. O'Brien, F. Reidl n, T. Reiter * & n
author keywords: Metagenomics; Sequence assembly; Strain variation; Bounded expansion; Dominating set
MeSH headings : Algorithms; Genetic Variation; Genome; Metagenomics / methods; Software
TL;DR:
An information retrieval system for large metagenomic data sets that exploits the sparsity of DNA assembly graphs to efficiently extract subgraphs surrounding an inferred genome is introduced.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
15. Life on Land
(Web of Science)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: August 10, 2020
2020 journal article
Polynomial Treedepth Bounds in Linear Colorings
ALGORITHMICA, 83(1), 361–386.
Contributors: J. Kun*, M. O’Brien n, M. Pilipczuk * & n
author keywords: Linear colorings; p-centered colorings; Bounded expansion; Treedepth
TL;DR:
A polynomial upper bound on the treedepth in general graphs is established, and tighter bounds in trees and interval graphs via constructive coloring algorithms are given via constructive coloring algorithms.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
11. Sustainable Cities and Communities
(Web of Science)
Sources: Web Of Science, ORCID, NC State University Libraries
Added: September 21, 2020
2020 chapter
Secondary Structure Ensemble Analysis via Community Detection
In Association for Women in Mathematics Series (Vol. 22, pp. 55–81).
Contributors: H. Du*, M. Ferrari *, C. Heitsch *, F. Hurley n, C. Mennicke n, * , B. Xu *
Source: ORCID
Added: August 6, 2022
2019 conference paper
Approximating vertex cover using structural rounding
Proceedings of the Workshop on Algorithm Engineering and Experiments, 2020-January, 70–80.
Contributors: B. Lavallee *, H. Russell*, * & A. Poel*
TL;DR:
This work provides the first practical evaluation of the structural rounding framework for approximation algorithms, and finds that in this setting, structural rounding significantly outperforms standard 2-approximations.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2019 article
Approximating vertex cover using structural rounding
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85094768942&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2019 article
Faster Biclique Mining in Near-Bipartite Graphs
ANALYSIS OF EXPERIMENTAL ALGORITHMS, SEA2 2019, Vol. 11544, pp. 424–453.
author keywords: Bicliques; Odd cycle transversal; Bipartite; Enumeration algorithms; Parameterized complexity
TL;DR:
Two new algorithms optimized for near-bipartite graphs are introduced - one which enumerates MIBs in time O(M_I |V||E| k), and another based on the approach of Alexe et al. which enumeration of all maximal bicliques in time M_I and M_B, where M-I andM_B denote the number of M IBs and MBs in the graph, respectively.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
11. Sustainable Cities and Communities
(Web of Science)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: November 16, 2020
2019 conference paper
Mining maximal induced bicliques using odd cycle transversals
SIAM International Conference on Data Mining, SDM 2019, 324–332.
TL;DR:
A new algorithm for enumerating MIBs in general graphs, whose run time depends on how "close to bipartite" the input is, and the runtime is parameterized by the size k of an odd cycle transversal (OCT), a vertex set whose deletion results in a bipartITE graph.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2019 article
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
27TH ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS (ESA 2019), Vol. 144.
Contributors: E. Demaine, T. Goodrich, K. Kloster, B. Lavallee, Q. Liu, , A. Vakilian, A. Poel
author keywords: structural rounding; graph editing; approximation algorithms
TL;DR:
New editing algorithms are developed that find the approximately-fewest edits required to bring a given graph into one of several important graph classes (in some cases, also approximating the target parameter of the family).
(via Semantic Scholar)
UN Sustainable Development Goal Categories
11. Sustainable Cities and Communities
(Web of Science)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: October 5, 2020
2019 journal article
Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs
Journal of Computer and System Sciences, 105, 199–241.
Contributors: E. Demaine *, F. Reidl *, P. Rossmanith *, F. Sánchez Villaamil*, S. Sikdar* & n
author keywords: Structural sparsity; Bounded expansion; Complex networks; Random graphs; Motif counting; Centrality measures
TL;DR:
This research establishes that many real-world networks exhibit bounded expansion, a strong notion of structural sparsity, and demonstrates that it can be leveraged to design efficient algorithms for network analysis, and supports the findings with empirical measurements on a corpus of real- world networks.
(via Semantic Scholar)
Source: ORCID
Added: May 25, 2019
2019 journal article
Subgraph centrality and walk-regularity
Linear Algebra and Its Applications, 570, 225–244.
Contributors: E. Horton n, K. Kloster n & n
author keywords: Centrality; Graph entropy; Walk-regularity; Functions of matrices; Network analysis
TL;DR:
This work considers when non--walk-regular graphs can achieve maximum entropy, calling such graphs $\textit{entropic}$, and builds infinite families of entropic graphs, as well as a family of witnessing parameters with a limit point at zero.
(via Semantic Scholar)
Source: ORCID
Added: February 12, 2019
2018 conference paper
A practical fpt algorithm for flow decomposition and transcript assembly
Proceedings of the Workshop on Algorithm Engineering and Experiments, 2018-January, 75–86.
TL;DR:
The Flow Decomposition problem, which asks for the smallest set of weighted paths that "covers" a flow on a DAG, has recently been used as an important computational step in transcript assembly and it is proved the problem is in FPT when parameterized by the number of paths by giving a practical linear fpt algorithm.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2018 article
An updated experimental evaluation of graph bipartization methods
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85104339918&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2018 journal article
Benchmarking treewidth as a practical component of tensor network simulations
PLOS ONE, 13(12).
Contributors: E. Dumitrescu *, A. Fisher n, T. Goodrich n, T. Humble *, n & A. Wright n
Ed(s): E. Torre
MeSH headings : Algorithms; Benchmarking; Computer Graphics; Computer Simulation; Quantum Theory; Software
TL;DR:
This work exhibits multiple regimes where treewidth-based algorithms outperform domain-specific algorithms, while demonstrating that the optimal choice of algorithm has a complex dependence on the network density, expected contraction complexity, and user run time requirements.
(via Semantic Scholar)
Sources: Web Of Science, ORCID, NC State University Libraries
Added: January 7, 2019
2018 article
Benchmarking treewidth as a practical component of tensor-network–based quantum simulation
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85095245427&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2018 article
Exploring neighborhoods in large metagenome assembly graphs reveals hidden sequence diversity
Brown, C. T., Moritz, D., O’Brien, M. P., Reidl, F., Reiter, T., & Sullivan, B. D. (2018, November 5). BioRxiv, Vol. 11.
Contributors: C. Brown, D. Moritz *, M. O’Brien *, F. Reidl *, T. Reiter & *
TL;DR:
An information retrieval system for large metagenomic data sets that exploits the sparsity of DNA assembly graphs to efficiently extract subgraphs surround-ing an inferred genome is introduced.
(via Semantic Scholar)
Source: ORCID
Added: February 8, 2019
2018 article
Mining maximal induced bicliques using odd cycle transversals
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85093320378&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2018 journal article
Optimizing adiabatic quantum program compilation using a graph-theoretic framework
Quantum Information Processing, 17(5).
Contributors: T. Goodrich n, n & T. Humble *
TL;DR:
This work develops a new baseline for embedding a wide range of optimization problems into fault-free D-Wave annealing hardware, and introduces a graph-theoretic framework for developing structured embedding algorithms.
(via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020
2018 article
Polynomial treedepth bounds in linear colorings
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85092833264&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2018 article
Structural rounding: Approximation algorithms for graphs near an algorithmically tractable class
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85094277709&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2018 article
Subgraph centrality and walk-regularity
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85093754399&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2018 chapter
Treedepth Bounds in Linear Colorings
In Graph-Theoretic Concepts in Computer Science: Vol. 11159 LNCS (pp. 331–343).
Contributors: J. Kun*, M. O’Brien n & n
TL;DR:
Low-treedepth colorings are introduced as an alternative to the commonly used p-centered colorings and a co-NP-completeness reduction is given for recognizing p-linear colorings, and polynomial upper bounds are established via constructive coloring algorithms in trees and intervals graphs and it is conjecture that aPolynomial relationship is in fact the worst case in general graphs.
(via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020
2018 journal article
Walk entropy and walk-regularity
Linear Algebra and Its Applications, 546, 115–121.
Contributors: K. Kloster n, D. Král * & n
author keywords: Graph entropy; Walk-regularity; Subgraph centrality; Matrix exponential
Source: ORCID
Added: February 8, 2019
2017 article
A practical fpt algorithm for flow decomposition and transcript assembly
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85094353595&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2017 article
An experimental evaluation of a bounded expansion algorithmic pipeline
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85092949285&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2017 conference paper
Asymptotic analysis of equivalences and core-structures in kronecker-style graph models
Proceedings - IEEE International Conference on Data Mining, ICDM, 829–834.
Source: ORCID
Added: August 6, 2022
2017 conference paper
Being even slightly shallow makes life hard
Leibniz International Proceedings in Informatics, LIPIcs, 83.
Contributors: I. Muzi *, . M.P. O'Brien, F. Reidl * & n
TL;DR:
Dense $r/2$-Shallow Topological Minor and Dense £r-Subdivsion are already NP-hard for r = 1$ in very sparse graphs and do not admit algorithms with running time $2^{o(\mathbf{tw}^2)} n^{O(1)}$ when parameterized by the treewidth of the input graph for $r \geq 2$ unless ETH fails.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2017 article
Being even slightly shallow makes life hard
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85094429786&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2017 article
Optimizing Adiabatic Quantum Program Compilation using a Graph-Theoretic Framework
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85095056109&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2017 article
Walk entropy and walk-regularity
ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85094268676&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2016 conference paper
A fast parameterized algorithm for Co-Path Set
Leibniz International Proceedings in Informatics, LIPIcs, 63.
TL;DR:
A linear-time fpt algorithm with complexity O^*(1.588^k) for deciding k-CO-PATH SET is given, significantly improving the previously best known O*(2.17^ k) of Feng, Zhou, and Wang (2015).
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2016 journal article
A multi-level anomaly detection algorithm for time-varying graph data with interactive visualization
Social Network Analysis and Mining, 6(1).
Contributors: R. Bridges *, J. Collins *, E. Ferragut*, J. Laska * & n
author keywords: Anomaly detection; Graph sequence; Visualization
TL;DR:
A new graph model is introduced, a generalization of the BTER model of Seshadhri et al., by adding flexibility to community structure, and this model is used to perform multi-scale graph anomaly detection and provides insight into a graph’s structure and internal context that may shed light on a detected event.
(via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020
2016 conference paper
Asymptotic analysis of equivalences and core-structures in Kronecker-style graph models
2016 ieee 16th international conference on data mining (icdm), 829–834.
TL;DR:
It is proved that although several R-MAT formulations are asymptotically equivalent, their behaviour is different from that of SKG, and a case where asymPTotic analysis reveals unexpected behavior within a given model is considered.
(via Semantic Scholar)
Sources: NC State University Libraries, NC State University Libraries, ORCID
Added: August 6, 2018
2016 journal article
Tree decompositions and social graphs
INTERNET MATHEMATICS, 12(5), 315–361.
Contributors: A. Adcock*, n & M. Mahoney *
TL;DR:
It is shown that TD methods can identify structures that correlate strongly with the core-periphery structure of realistic networks, even when using simple greedy heuristics; and it is proved that the only two impediments to low-distortion hyperbolic embedding are high tree-width and long geodesic cycles.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
10. Reduced Inequalities
(OpenAlex)
11. Sustainable Cities and Communities
(Web of Science)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: August 6, 2018
2015 article
Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs
ALGORITHMS AND MODELS FOR THE WEB GRAPH, (WAW 2015), Vol. 9479, pp. 29–41.
Contributors: M. Farrell *, T. Goodrich n, N. Lemons*, F. Reidl *, F. Villaamil* & n
Sources: Web Of Science, NC State University Libraries, ORCID
Added: August 6, 2018
2015 article
Multi-Level Anomaly Detection on Time-Varying Graph Data
PROCEEDINGS OF THE 2015 IEEE/ACM INTERNATIONAL CONFERENCE ON ADVANCES IN SOCIAL NETWORKS ANALYSIS AND MINING (ASONAM 2015), pp. 579–583.
Contributors: R. Bridges *, J. Collins *, E. Ferragut*, J. Laska * & n
TL;DR:
This work introduces a generalization of the BTER model of Seshadhri et al. by adding flexibility to community structure, and uses this model to perform multi-scale graph anomaly detection, accurately detecting anomalies at the node, subgraph, and graph levels.
(via Semantic Scholar)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: August 6, 2018
2015 article
On the Threshold of Intractability
ALGORITHMS - ESA 2015, Vol. 9294, pp. 411–423.
Contributors: P. Drange *, M. Dregi*, D. Lokshtanov * & n
TL;DR:
This article shows that both graph modification problems are Open image in new window -hard, resolving a conjecture by Natanzon, Shamir, and Sharan (2001), and gives a subexponential time parameterized algorithm solving this problem.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
11. Sustainable Cities and Communities
(Web of Science)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: August 6, 2018
2015 journal article
Zig-Zag Numberlink is NP-Complete
Journal of Information Processing, 23(3), 239–245.
Contributors: A. Adcock*, E. Demaine *, M. Demaine*, . M.P. O'Brien, F. Reidl *, F. Villaamil*, n
TL;DR:
The hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the ``cover all vertices'' constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2014 journal article
An integrated programming and development environment for adiabatic quantum optimization
Computational Science and Discovery, 7(1).
Contributors: T. Humble *, A. McCaskey *, R. Bennink *, J. Billings *, E. Dazevedo *, * , C. Klymko*, H. Seddiqi*
TL;DR:
An integrated programming and development environment for AQO called Jade Adiabatic Development Environment (JADE) is presented that provides control over all the steps taken during program synthesis and its potential use for benchmarking AQO programs by the quantum computer science community is discussed.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2014 conference paper
Locally Estimating Core Numbers
Proceedings - IEEE International Conference on Data Mining, ICDM, 2015-January(January), 460–469.
Contributors: M. Obrien n & n
TL;DR:
A new method for estimating the core number based only on the properties of the graph within a region of radius δ around the vertex is introduced, and an asymptotic error bound of the estimator on random graphs is proved.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2013 journal article
Adiabatic quantum programming: minor embedding with hard faults
Quantum Information Processing, 13(3), 709–729.
Contributors: C. Klymko*, n & T. Humble *
author keywords: Quantum computing; Adiabatic quantum optimization; Graph embedding; Fault-tolerant computing
TL;DR:
Algorithms for embedding arbitrary instances of the adiabatic quantum optimization algorithm into a square lattice of specialized unit cells are presented and are shown to be more resilient to faulty fabrics than naive embedding approaches.
(via Semantic Scholar)
Sources: ORCID, Crossref, NC State University Libraries
Added: February 5, 2020
2013 chapter
Evaluating OpenMP Tasking at Scale for the Computation of Graph Hyperbolicity
In OpenMP in the Era of Low Power Devices and Accelerators: Vol. 8122 LNCS (pp. 71–83).
Contributors: A. Adcock*, * , O. Hernandez* & M. Mahoney *
TL;DR:
It is found that multiple task levels permits finer grained tasks at runtime and results in better performance at scale than worksharing constructs in OpenMP 3.1.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
8. Decent Work and Economic Growth
(OpenAlex)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020
2013 journal article
On a conjecture of Andrica and Tomescu
Journal of Integer Sequences, 16(3). http://www.scopus.com/inward/record.url?eid=2-s2.0-84880061040&partnerID=MN8TOARS
Source: ORCID
Added: August 6, 2022
2013 conference paper
Parallel algorithms for graph optimization using tree decompositions
Proceedings - IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW 2013, 1838–1847.
TL;DR:
This work enables a significant expansion of the scale of graphs on which exact solutions to maximum weighted independent set can be obtained, and forms a framework for solving additional graph optimization problems with similar techniques.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2013 conference paper
Tree-Like Structure in Large Social and Information Networks
2013 IEEE 13th International Conference on Data Mining, 1–10.
TL;DR:
A detailed empirical analysis of the tree-like properties of realistic informatics graphs is performed using two very different notions of tree-likeness: Gromov's d-hyperbolicity and tree decompositions, tools from structural graph theory which measure how tree- like a graph is in terms of its cut structure.
(via Semantic Scholar)
Source: ORCID
Added: August 6, 2022
2011 journal article
A mathematical analysis of the R-MAT random graph generator
Networks, 58(3), 159–170.
author keywords: random graph; scale-free graph; R-MAT generator; occupancy problem
TL;DR:
This article analyzes the graphs generated by R‐MAT and model the generator in terms of occupancy problems to prove results about the degree distributions of these graphs, and proves that the limiting degree distributions can be expressed as a mixture of normal distributions with means and variances.
(via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020
2009 journal article
Counting paths in digraphs
European Journal of Combinatorics, 31(3), 961–975.
Contributors: P. Seymour * & *
TL;DR:
The problem of bounding the number of (non-induced) 4-vertex paths in 3-free digraphs is studied and an upper bound of 4n^4/75 is shown using Bondy's result for Thomasse's conjecture.
(via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020
2008 journal article
Cycles in dense digraphs
Combinatorica, 28(1), 1–18.
Contributors: M. Chudnovsky *, P. Seymour * & *
TL;DR:
It is proved that in general β(G) ≤ γ(G), and that in two special cases: when V (G) is the union of two cliques when the vertices of G can be arranged in a circle such that if distinct u, v, w are in clockwise order and uw is a (directed) edge, then so are both uv, vw.
(via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020
Employment
Updated: November 5th, 2019 16:58
2019 - present
University of Utah Salt Lake City, UT, US
Associate Professor
School of Computing
2013 - 2019
North Carolina State University Raleigh, NC, US
Computer Science
2008 - 2013
Oak Ridge National Laboratory Oak Ridge, TN, US
Computer Science & Mathematics Division
Education
Updated: July 7th, 2016 16:55
2003 - 2008
Princeton University Princeton, NJ, US
PhD Mathematics
Mathematics
1999 - 2003
Georgia Institute of Technology Atlanta, GA, US
B.S. Applied Mathematics; B.S. Computer Science
Citation Index includes data from a number of different sources. If you have questions about the sources of data in the Citation Index or need a set of data which is free to re-distribute, please contact us.
Certain data included herein are derived from the Web of Science© and InCites© (2024) of Clarivate Analytics. All rights reserved. You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.