Search Results

Documents authored by McConnell, Ross M.

Found 2 Possible Name Variants:

McConnell, Ross M.

Document
DOI: 10.4230/LIPIcs.MFCS.2018.68
Interval-Like Graphs and Digraphs

Authors: Pavol Hell, Jing Huang, Ross M. McConnell, and Arash Rafiey

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We unify several seemingly different graph and digraph classes under one umbrella. These classes are all, broadly speaking, different generalizations of interval graphs, and include, in addition to interval graphs, adjusted interval digraphs, threshold graphs, complements of threshold tolerance graphs (known as `co-TT' graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray graphs. (The last three classes coincide, but have been investigated in different contexts.) This common view is made possible by introducing reflexive relationships (loops) into the analysis. We also show that all the above classes are united by a common ordering characterization, the existence of a min ordering. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, and show that they are precisely the digraphs that are characterized by the existence of a min ordering. We also offer an alternative geometric characterization of these digraphs. For most of the above graph and digraph classes, we show that they are exactly those signed-interval digraphs that satisfy a suitable natural restriction on the digraph, like having a loop on every vertex, or having a symmetric edge-set, or being bipartite. For instance, co-TT graphs are precisely those signed-interval digraphs that have each edge symmetric. We also offer some discussion of future work on recognition algorithms and characterizations.
Cite as

Pavol Hell, Jing Huang, Ross M. McConnell, and Arash Rafiey. Interval-Like Graphs and Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 68:1-68:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hell_et_al:LIPIcs.MFCS.2018.68,
  author =	{Hell, Pavol and Huang, Jing and McConnell, Ross M. and Rafiey, Arash},
  title =	{{Interval-Like Graphs and Digraphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{68:1--68:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.68},
  URN =		{urn:nbn:de:0030-drops-96503},
  doi =		{10.4230/LIPIcs.MFCS.2018.68},
  annote =	{Keywords: graph theory, interval graphs, interval bigraphs, min ordering, co-TT graph}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.69
Double Threshold Digraphs

Authors: Peter Hamburger, Ross M. McConnell, Attila Pór, Jeremy P. Spinrad, and Zhisheng Xu

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
A semiorder is a model of preference relations where each element x is associated with a utility value alpha(x), and there is a threshold t such that y is preferred to x iff alpha(y) - alpha(x) > t. These are motivated by the notion that there is some uncertainty in the utility values we assign an object or that a subject may be unable to distinguish a preference between objects whose values are close. However, they fail to model the well-known phenomenon that preferences are not always transitive. Also, if we are uncertain of the utility values, it is not logical that preference is determined absolutely by a comparison of them with an exact threshold. We propose a new model in which there are two thresholds, t_1 and t_2; if the difference alpha(y) - alpha(x) is less than t_1, then y is not preferred to x; if the difference is greater than t_2 then y is preferred to x; if it is between t_1 and t_2, then y may or may not be preferred to x. We call such a relation a (t_1,t_2) double-threshold semiorder, and the corresponding directed graph G = (V,E) a (t_1,t_2) double-threshold digraph. Every directed acyclic graph is a double-threshold digraph; increasing bounds on t_2/t_1 give a nested hierarchy of subclasses of the directed acyclic graphs. In this paper we characterize the subclasses in terms of forbidden subgraphs, and give algorithms for finding an assignment of utility values that explains the relation in terms of a given (t_1,t_2) or else produces a forbidden subgraph, and finding the minimum value lambda of t_2/t_1 that is satisfiable for a given directed acyclic graph. We show that lambda gives a useful measure of the complexity of a directed acyclic graph with respect to several optimization problems that are NP-hard on arbitrary directed acyclic graphs.
Cite as

Peter Hamburger, Ross M. McConnell, Attila Pór, Jeremy P. Spinrad, and Zhisheng Xu. Double Threshold Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 69:1-69:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hamburger_et_al:LIPIcs.MFCS.2018.69,
  author =	{Hamburger, Peter and McConnell, Ross M. and P\'{o}r, Attila and Spinrad, Jeremy P. and Xu, Zhisheng},
  title =	{{Double Threshold Digraphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{69:1--69:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.69},
  URN =		{urn:nbn:de:0030-drops-96519},
  doi =		{10.4230/LIPIcs.MFCS.2018.69},
  annote =	{Keywords: posets, preference relations, approximation algorithms}
}

McConnell, Ross

Document
DOI: 10.4230/DagRep.1.5.29
Exploiting graph structure to cope with hard problems (Dagstuhl Seminar 11182)

Authors: Andreas Brandstädt, Martin Charles Golumbic, Pinar Heggernes, and Ross McConnell

Published in: Dagstuhl Reports, Volume 1, Issue 5 (2011)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11182 ``Exploiting graph structure to cope with hard problems'' which has been held in Schloss Dagstuhl -- Leibniz Center for Informatics from May 1st, 2011 to May 6th, 2011. During the seminar experts with a common focus on graph algorithms presented various new results in how to attack NP-hard graph problems by using the structure of the input graph. Moreover, in the afternoon of each seminar's day new problems have been posed and discussed.
Cite as

Andreas Brandstädt, Martin Charles Golumbic, Pinar Heggernes, and Ross McConnell. Exploiting graph structure to cope with hard problems (Dagstuhl Seminar 11182). In Dagstuhl Reports, Volume 1, Issue 5, pp. 29-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{brandstadt_et_al:DagRep.1.5.29,
  author =	{Brandst\"{a}dt, Andreas and Golumbic, Martin Charles and Heggernes, Pinar and McConnell, Ross},
  title =	{{Exploiting graph structure to cope with hard problems (Dagstuhl Seminar 11182)}},
  pages =	{29--46},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{5},
  editor =	{Brandst\"{a}dt, Andreas and Golumbic, Martin Charles and Heggernes, Pinar and McConnell, Ross},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.5.29},
  URN =		{urn:nbn:de:0030-drops-32027},
  doi =		{10.4230/DagRep.1.5.29},
  annote =	{Keywords: Graph Classes, Graph Algorithms, NP-completeness, Width Parameters, Approximation Algorithms, Parameterized Complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact